二分搜索及其于不同场景的应用(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

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注