二分法：算法刷题中的经典题目

在算法刷题中，二分法是一个非常重要的算法技巧。二分法也称为二分搜索，它的基本思想是通过不断将搜索区间一分为二，缩小搜索范围，最终找到目标元素或确定目标元素不存在。二分法适用于有序数据集的查找，时间复杂度为O(log n)。

下面我们通过具体实例来解析二分法的应用。

例题1：寻找有序数组中的指定元素

题目描述：给定一个有序数组和一个目标值，请你在该数组中查找是否有目标值，并返回其索引。如果数组中不存在目标值，则返回-1。

解题思路：使用二分法进行有序数组的查找。每次将数组中间元素与目标值进行比较，如果中间元素等于目标值，则返回中间元素的索引；如果目标值小于中间元素，则在左半部分数组继续查找；如果目标值大于中间元素，则在右半部分数组继续查找。重复上述步骤，直到找到目标值或搜索区间为空。

示例代码（Python）：

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif target < nums[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return -1

例题2：寻找有序数组中的第k小元素

题目描述：给定一个有序数组和一个整数k，请你在该数组中找到第k小的元素。注意，数组中的元素可能重复。

解题思路：使用二分法进行有序数组的第k小元素的查找。首先将数组中间元素与第k小元素进行比较，如果中间元素等于第k小元素，则返回中间元素；如果中间元素小于第k小元素，则在右半部分数组继续查找；如果中间元素大于第k小元素，则在左半部分数组继续查找。重复上述步骤，直到找到第k小元素或搜索区间为空。

示例代码（Python）：

def findKthSmallest(nums, k):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == k:
            return mid
        elif nums[mid] < k:
            left = mid + 1
        else:
            right = mid - 1
    return -1

例题3：寻找旋转排序数组中的最小值

题目描述：给定一个旋转排序数组（即升序数组中某一段被旋转到数组前方），请你在原地对数组进行排序，使其变为升序数组。注意，题目要求不能使用额外的空间。

解题思路：使用二分法寻找旋转排序数组中的最小值。首先确定最小值的左右边界，然后使用二分法在左半部分数组中查找最小值的位置。在查找过程中，利用已找到的最小值将左半部分数组分为两部分，确保左半部分数组有序且最小值位于右半部分数组中。重复上述步骤，直到找到最小值或搜索区间为空。最后将最小值与右边界交换即可完成原地排序。

示例代码（Python）：

由于篇幅限制，此处省略代码示例。请注意，代码示例中的逻辑较为复杂，需要仔细理解二分法的应用和原地排序的思路。