二分搜索及其于不同场景的应用(C/Java/Python)

算法目录

二分搜索的思想

• 在一个连续的有序数组中，通过比较中间值与目标值的大小，每次缩减一半的搜索范围，逐次缩减后，找到目标值所在位置。
  • 例如，对于长度为8的数组nums = {1, 2, 3, 4, 5, 7, 8, 9}，需要搜索值为6的元素在数组内的位置：
    • 比较中间值nums[ (0 + 7) / 2 ] 与 target值，即nums[3] 与 6，可知nums[3] < 6。
    • 左边界设置成之前的中间位置，继续比较中间值nums[ (3 + 7) / 2 ] 与 target值，即nums[5] 与 6，可知nums[5] > 6。
    • 右边界设置成之前的中间位置，继续比较中间值nums[ (3 + 5) / 2]与 target值，即nums[4] 与 6，可知nums[4] < 6。
    • 左边界设置成之前的中间位置，此时比较范围在nums[4 ~ 5]，边界相邻，直接比较nums[4]与6，nums[5]与6，可知两边界均不等于6。
    • 返回-1，表示该值不在该数组中。
  • 它的时间复杂度为O(logn)。

二分搜索的应用

1. 最简单的，在连续有序数组中的非递归二分搜索：LeetCode-简单-35-搜索插入位置(Java)
   • 单纯的只需要找到这个唯一值的位置。
2. 偏移后的连续有序数组中的递归二分搜索：LeetCode-中等-33-搜索旋转排序数组-二分法(C)
   • 这个有序数组被偏移了，从12345变成了45123。
3. 利用二分搜索寻找连续有序数组中，一连续相同数字段的开头与结尾：LeetCode-中等进阶-34-在排序数组中查找元素的第一个和最后一个位置-二分法(C)
   • 要搜索两个值：
     • 一个值等于target，且前面的值小于它，
     • 第二个值也等于target，但其后面的值大于它。
4. 搜索一被无用信息分割开的有序数组中，最后一个大于target值的元素：LeetCode-困难-239-滑动窗口的最大值-队列/二分法(C)
   • 有一个队列，占用一定长数组的部分空间，它的队头可能在队尾前面，也可能在队尾后面。
     • 它可能长这样：
       • 12345----
       • 45----123
       • --12345--
     • 其中，数字1表示队头，数字5表示队尾，-表示该位置不属于队列中元素。
   • 在这个队列数组中，需要找到最后一个大于target的值。

二分搜索的格式

• 递归：
  1. int binarySearch(int* nums, int left, int right, int target)
     • 其中，nums为待搜索数组，left与right分别为左右边界，target为待搜索的值。
     • 进行递归调用时，一定要用return binarySearch()才能正确返回结果。
  2. 先使用mid = (left + right) / 2获得中间位置，方便后续调用。
  3. 再比较left、right的值：
     • 先比较边界可以减少一定计算量：
       • 比如一个长度为10000的数组，target值恰巧在左边界上，
       • 如果是先比较中间的值，那一般代码就直接将中间值变为右边界继续搜索，左边界的位置不会被比较
       • 从nums[0 ~ 9999]，nums[0, 4999]，nums[0, 2499]一直比较到nums[0, 1]才会因为触发left + 1 == right，才会搜索到nums[0]。
       • 如果target恰巧在右边界上，同理。
  4. 再比较left + 1 == right：
     • 如果相同，说明此时比较范围仅剩下左右边界的值，
     • 由第3条件可知：左右边界都不等于target，返回-1，表示该值不在nums中。
  5. 再比较mid的值：
     • 如果数组为升序数组，且mid值小于target值，则递归比较nums[mid, right]，即binarySearch(nums, mid, right, target)
       • 升序，大于，递归比较nums[left, mid]
       • 降序，小于，递归比较nums[left, mid]
       • 降序，大于，递归比较nums[mid, right]
       • 升序降序和大于小于都挺好判断的，需要用的时候现场判断一下就好，不用记。
       • 如果等于就直接返回mid值了。
  6. 注：
     • Leetcode的编译器要求函数必须有返回值，所以最后可以加一个 return -1;虽然不会被触发，但是不加它无法编译。
     • 此外，递归的函数调用时，一定要使用return binarySearch();的方法调用，否则出不来正确结果。
• 非递归：
  • int binarySearch(int* nums, int numsLength, int target)
    • 其中，nums是待搜索数组，numsLength是数组长度，target是目标值。
  • 非递归和递归不能说一模一样吧，但复制粘贴只要改几个地方是没错的。
    • 思想是一样的，就是部分地方改一下就好，可以看下后面代码的区别。

C代码

//测试代码主函数
int main(){
    int nums[] = {1, 2, 3, 4, 5, 7, 8, 9};
    int target = 999;
    printf("%d", binarySearch2(nums, 8, target));
    printf("%d", binarySearch(nums, 0, 7, target));
    return 0;
}

//递归二分搜索升序数组
int binarySearch(int* nums, int left, int right, int target){
    int mid = ( left + right ) / 2;
    if(nums[left] == target) return left;
    else if(nums[right] == target) return right;
    else if(left + 1 == right) return -1;
    else if(nums[mid] == target) return mid;
    else if(nums[mid] > target) return binarySearch(nums, left, mid, target);
    else if(nums[mid] < target) return binarySearch(nums, mid, right, target);
    return -1;
} 

//非递归二分搜索升序数组
int binarySearch2(int* nums, int numsLength, int target){
    int left = 0;
    int right = numsLength - 1;
    int mid;
    while(1){
        mid = (left + right) / 2;
        if(nums[left] == target) return left;
        else if(nums[right] == target) return right;
        else if(left + 1 == right) return -1;
        else if(nums[mid] == target) return mid;
        else if(nums[mid] > target) right = mid;
        else if(nums[mid] < target) left = mid;
    }
} 

Java代码

//测试代码主函数
public static void main(String args[]){
    int[] nums = {1, 2, 3, 4, 5, 7, 8, 9};
    int target = 9;
    System.out.println(binarySearch(nums, 0, 7, target));
    System.out.println(binarySearch2(nums, 8, target));
}

//递归二分搜索升序数组
static int binarySearch(int[] nums, int left, int right, int target){
    int mid = ( left + right ) / 2;
    if(nums[left] == target) return left;
    else if(nums[right] == target) return right;
    else if(left + 1 == right) return -1;
    else if(nums[mid] == target) return mid;
    else if(nums[mid] > target) return binarySearch(nums, left, mid, target);
    else if(nums[mid] < target) return binarySearch(nums, mid, right, target);
    return -1;
} 

//非递归二分搜索升序数组
static int binarySearch2(int[] nums, int numsLength, int target){
    int left = 0;
    int right = numsLength - 1;
    int mid;
    while(true){
        mid = (left + right) / 2;
        if(nums[left] == target) return left;
        else if(nums[right] == target) return right;
        else if(left + 1 == right) return -1;
        else if(nums[mid] == target) return mid;
        else if(nums[mid] > target) right = mid;
        else if(nums[mid] < target) left = mid;
    }
} 

python代码

#测试函数
nums = [1, 2, 3, 4, 5, 7, 8, 9]
target = 999
print(binarySearch(nums, 0, 7, target))
print(binarySearch2(nums, 8, target))

#递归二分搜索升序数组
def binarySearch(nums, left, right, target):
    mid = (left + right) // 2
    if nums[left] == target:
        return left
    elif nums[right] == target:
        return right
    elif left + 1 == right:
        return -1
    elif nums[mid] == target:
        return mid
    elif nums[mid] > target:
        return binarySearch(nums, left, mid, target)
    elif nums[mid] < target:
        return binarySearch(nums, mid, right, target)
    return -1

#非递归二分搜索升序数组
def binarySearch2(nums, numsLength, target):
    left = 0
    right = numsLength - 1
    while True :
        mid = (left + right) // 2
        if nums[left] == target:
            return left
        elif nums[right] == target:
            return right
        elif left + 1 == right:
            return -1
        elif nums[mid] == target:
            return mid
        elif nums[mid] > target:
            right = mid
        elif nums[mid] < target:
            left = mid