二分查找

二分搜索（Binary Search）是一种在有序数组或列表中查找目标值的高效算法，其时间复杂度是 O(log n)。以下是一些经典的二分搜索题目及其示例：

1. 二分查找：查找目标值

题目描述： 给定一个升序排序的数组 nums 和一个目标值 target，请在数组中查找目标值的位置。如果目标值存在，则返回其索引；如果目标值不存在，则返回 -1。

示例代码（Kotlin）：

fun binarySearch(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val mid = left + (right - left) / 2
        if (nums[mid] == target) {
            return mid  // 找到目标值，返回索引
        } else if (nums[mid] < target) {
            left = mid + 1  // 目标值在右半部分
        } else {
            right = mid - 1  // 目标值在左半部分
        }
    }
    return -1  // 目标值不存在
}

fun main() {
    val nums = intArrayOf(1, 3, 5, 7, 9)
    println(binarySearch(nums, 5))  // 输出: 2
    println(binarySearch(nums, 8))  // 输出: -1
}

2. 寻找旋转排序数组中的最小值

题目描述： 给定一个已经升序排序的数组，但是该数组经过旋转，求旋转数组中的最小值。

示例代码（Kotlin）：

fun findMin(nums: IntArray): Int {
    var left = 0
    var right = nums.size - 1
    while (left < right) {
        val mid = left + (right - left) / 2
        if (nums[mid] > nums[right]) {
            left = mid + 1  // 最小值在右半部分
        } else {
            right = mid  // 最小值在左半部分
        }
    }
    return nums[left]  // left 就是最小值的索引
}

fun main() {
    val nums = intArrayOf(4, 5, 6, 7, 0, 1, 2)
    println(findMin(nums))  // 输出: 0
}

3. 寻找一个元素在有序数组中的位置（变种）

题目描述： 在一个升序排序的数组 nums 中，寻找目标值 target 的插入位置（即使目标值不存在，也应该返回目标值应当插入的位置）。

示例代码（Kotlin）：

fun searchInsert(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size
    while (left < right) {
        val mid = left + (right - left) / 2
        if (nums[mid] < target) {
            left = mid + 1  // 目标值在右半部分
        } else {
            right = mid  // 目标值在左半部分
        }
    }
    return left  // left 是目标值的插入位置
}

fun main() {
    val nums = intArrayOf(1, 3, 5, 6)
    println(searchInsert(nums, 5))  // 输出: 2
    println(searchInsert(nums, 2))  // 输出: 1
    println(searchInsert(nums, 7))  // 输出: 4
}

4. 查找旋转数组中的最大值

题目描述： 给定一个旋转的升序数组，找到该数组中的最大值。

示例代码（Kotlin）：

fun findMax(nums: IntArray): Int {
    var left = 0
    var right = nums.size - 1
    while (left < right) {
        val mid = left + (right - left) / 2
        if (nums[mid] > nums[right]) {
            left = mid + 1  // 最大值在左半部分
        } else {
            right = mid  // 最大值在右半部分
        }
    }
    return nums[left - 1]  // left 是最小值的索引，最大值在其左侧
}

fun main() {
    val nums = intArrayOf(4, 5, 6, 7, 0, 1, 2)
    println(findMax(nums))  // 输出: 7
}

5. 平方根的二分查找

题目描述： 给定一个非负整数 x，返回 x 的平方根（结果只保留整数部分，即向下取整）。

示例代码（Kotlin）：

fun mySqrt(x: Int): Int {
    var left = 0
    var right = x
    while (left <= right) {
        val mid = left + (right - left) / 2
        if (mid * mid == x) {
            return mid  // 找到精确平方根
        } else if (mid * mid < x) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return right  // 返回最大的整数平方根
}

fun main() {
    println(mySqrt(8))  // 输出: 2
    println(mySqrt(16))  // 输出: 4
}

6. 寻找一个数的第一个和最后一个位置

题目描述： 给定一个升序排序的数组 nums 和一个目标值 target，找出目标值在数组中的第一个和最后一个位置。如果目标值不存在，返回 [-1, -1]。

示例代码（Kotlin）：

fun searchRange(nums: IntArray, target: Int): IntArray {
    fun findFirst(): Int {
        var left = 0
        var right = nums.size
        while (left < right) {
            val mid = left + (right - left) / 2
            if (nums[mid] < target) {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return if (left < nums.size && nums[left] == target) left else -1
    }

    fun findLast(): Int {
        var left = 0
        var right = nums.size
        while (left < right) {
            val mid = left + (right - left) / 2
            if (nums[mid] <= target) {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return if (left > 0 && nums[left - 1] == target) left - 1 else -1
    }

    val first = findFirst()
    return if (first == -1) {
        intArrayOf(-1, -1)
    } else {
        intArrayOf(first, findLast())
    }
}

fun main() {
    val nums = intArrayOf(5, 7, 7, 8, 8, 10)
    println(searchRange(nums, 8).joinToString())  // 输出: 3, 4
}