专栏首页尾尾部落[算法总结] 二分查找

[算法总结] 二分查找

二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。

二分查找很好写,却很难写对,据统计只有10%的程序员可以写出没有bug的的二分查找代码。出错原因主要集中在判定条件和边界值的选择上,很容易就会导致越界或者死循环的情况。

下面对二分查找及其变形进行总结:

1. 最基本的二分查找

public int binarySearch(int[] A, int target, int n){
    int low = 0, high = n, mid;
    while(low <= high){
        mid = low + (high - low) / 2;
        if(A[mid] == target){
            return mid;
        }else if(A[mid] > target){
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    return -1;
}

其中,有几个要注意的点: 1. 循环的判定条件是:low <= high 2. 为了防止数值溢出,mid = low + (high - low)/2 3. 当 A[mid]不等于target时,high = mid - 1low = mid + 1

leetcode参考:Search Insert Position

2. 查找目标值区域的左边界/查找与目标值相等的第一个位置/查找第一个不小于目标值数的位置

A = [1,3,3,5, 7 ,7,7,7,8,14,14] target = 7 return 4

public int binarySearchLowerBound(int[] A, int target, int n){
    int low = 0, high = n, mid;
    while(low <= high){
        mid = low + (high - low) / 2;
        if(target <= A[mid]){
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    if(low < A.length && A[low] == target)
        return low;
    else
        return -1;
}

3. 查找目标值区域的右边界/查找与目标值相等的最后一个位置/查找最后一个不大于目标值数的位置

A = [1,3,3,5,7,7,7, 7 ,8,14,14] target = 7 return 7

public int binarySearchUpperBound(int[] A, int target, int n){
    int low = 0, high = n, mid;
    while(low <= high){
        mid = low + (high - low) / 2;
        if(target >= A[mid]){
            low = mid + 1;
        }else{
            high = mid - 1;
        }
    }
    if(high >= 0 && A[high] == target)
        return high;
    else
        return -1;
}

此题以可变形为查找第一个大于目标值的数/查找比目标值大但是最接近目标值的数,我们已经找到了最后一个不大于目标值的数,那么再往后进一位,返回high + 1,就是第一个大于目标值的数。

剑指offer:数字在排序数组中出现的次数

4. 查找最后一个小于目标值的数/查找比目标值小但是最接近目标值的数

此题以可由第 2 题变形而来,我们已经找到了目标值区域的下(左)边界,那么再往左退一位,即low - 1,就是最后一个小于目标值的数。其实low - 1也是退出循环后high的值,因为此时 high刚好等于low - 1,它小于low,所以 while 循环结束。我们只要判断high是否超出边界即可。

A = [1,3,3, 5 ,7,7,7,7,8,14,14] target = 7 return 3

int low = 0, high = n, mid;
while(low <= high){
    mid = low + (high - low) / 2;
    if(target <= A[mid]){
        high = mid - 1;
    }else{
        low = mid + 1;
    }
}
return high < 0 ? -1 : high;

5. 查找第一个大于目标值的数/查找比目标值大但是最接近目标值的数

此题以可由第 3 题变形而来,我们已经找到了目标值区域的上(右)边界,那么再往右进一位,即high + 1,就是第一个大于目标值的数。其实high + 1也是退出循环后low的值,因为此时 low刚好等于high + 1,它大于high,所以 while 循环结束。我们只要判断low是否超出边界即可。

A = [1,3,3,5,7,7,7,7, 8 ,14,14] target = 7 return 8

int low = 0, high = n, mid;
while(low <= high){
    mid = low + (high - low) / 2;
    if(target >= A[mid]){
        low = mid + 1;
    }else{
        high = mid - 1;
    }
}
return low > n ? -1 : low;

6. 旋转数组返回最小元素

6.1 查找旋转数组的最小元素(假设不存在重复数字)

LeetCode: Find Minimum in Rotated Sorted Array Input: [3,4,5,1,2] Output: 1

public int findMin(int[] nums) {
    int len = nums.length;
    if(len == 0)
        return -1;
    int left = 0, right = len - 1, mid;

    while(left < right){
        mid = left + (right - left) / 2;
        if(nums[mid] > nums[right])
            left = mid + 1;
        else{
            right = mid;
        }
    }
    return nums[left];
}

注意这里和之前的二分查找的几点区别: 1. 循环判定条件为left < right,没有等于号 2. 循环中,通过比较nums[left]与num[mid]的值来判断mid所在的位置:

  • 如果nums[mid] > nums[right],说明前半部分是有序的,最小值在后半部分,令left = mid + 1
  • 如果nums[mid] <= num[right],说明最小值在前半部分,令right = mid

最后,left会指向最小值元素所在的位置。

6.2 查找旋转数组的最小元素(存在重复项)

LeetCode: Find Minimum in Rotated Sorted Array II 剑指offer:旋转数组的最小数字 Input: [2,2,2,0,1] Output: 0

public int findMin(int[] nums) {
    int len = nums.length;
    if(len == 0)
        return -1;
    int left = 0, right = len - 1, mid;
    while(left < right){
        mid = left + (right - left) / 2;
        if(nums[mid] > nums[right])
            left = mid + 1;
        else if(nums[mid] < nums[right])
            right = mid;
        else
            right--;
    }
    return nums[left];
}

和之前不存在重复项的差别是:当nums[mid] == nums[right]时,我们不能确定最小值在 mid的左边还是右边,所以我们就让右边界减一。

7. 在旋转排序数组中搜索

7.1 不考虑重复项

LeetCode: Search in Rotated Sorted Array

法一:

  • 先利用方法 6.1 查找数组中的最小元素,即确定分界点的位置
  • 把旋转的数组当成偏移,用(offset + mid) % len来求真实的 mid 的位置。
  • 然后用二分查找来定位目标值
public int search(int[] nums, int target) {
    int len = nums.length;
    if(len == 0)
        return -1;
    int left = 0, right = len - 1, mid;
    while(left < right){
        mid = left + (right - left) / 2;
        if(nums[mid] > nums[right])
            left = mid + 1;
        else
            right = mid;
    }
    int offset = left;
    left = 0;
    right = len - 1;
    while(left <= right){
        mid = left + (right - left) / 2;
        int realmid = (mid + offset) % len;
        if(nums[realmid] == target)
            return realmid;
        else if(nums[realmid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

法二:其实没有必要找到旋转数组的分界点,对于搜索左侧还是右侧我们是可以根据mid跟high的元素大小来判定出来的,直接根据target的值做二分搜索就可以了。

public int search(int[] nums, int target) {
    int len = nums.length;
    if(len == 0)
        return -1;
    int left = 0, right = len - 1, mid;
    while(left <= right){
        mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid;
        else if(nums[left] <= nums[mid]){
            if(target < nums[mid] && target >= nums[left])
                right = mid - 1;
            else
                left = mid + 1;
        }else if(nums[mid] <= nums[right]){
            if(target > nums[mid] && target <= nums[right])
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
    return -1;
}

7.2 存在重复项

LeetCode: Search in Rotated Sorted Array II

public boolean search(int[] nums, int target) {
    int len = nums.length;
    if(len == 0)
        return false;
    int left = 0, right = len - 1, mid;
    while(left <= right){
        mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return true;
        else if(nums[mid] > nums[right]){
            if(target < nums[mid] && target >= nums[left])
                right = mid;
            else
                left = mid + 1;
        }else if(nums[mid] < nums[right]){
            if(target > nums[mid] && target <= nums[right])
                left = mid + 1;
            else
                right = mid;
        }else{
            right --;
        }   
    }
    return false;
}

8. 二维数组中的查找

剑指offer:二维数组中的查找

二维数组是有序的,从右上角来看,向左数字递减,向下数字递增。因此可以利用二分查找的思想,从右上角出发:

  • 当要查找数字比右上角数字大时,下移;
  • 当要查找数字比右上角数字小时,左移;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [LeetCode]Degree of an Array 数组的度 [LeetCode]Degree of an Array 数组的度

    链接:https://leetcode.com/problems/degree-of-an-array/description/ 难度:Easy 题目:69...

    尾尾部落
  • [剑指offer] 数字在排序数组中出现的次数

    正常的思路就是二分查找了,我们用递归的方法实现了查找k第一次出现的下标,用循环的方法实现了查找k最后一次出现的下标。 除此之外,还有另一种奇妙的思路,因为da...

    尾尾部落
  • [LeetCode]Longest Continuous Increasing Subsequence 最长连续增长序列 [LeetCode]Longest Continuous Incr

    链接:https://leetcode.com/problems/longest-continuous-increasing-subsequence/descr...

    尾尾部落
  • LeetCode-15-3Sum

    Given an array S of n integers, are there elements a, b, c in S such that a + b ...

    欠扁的小篮子
  • 漫画:知乎面试题(旋转数组最小值Ⅱ - 进阶版)

    今天是小浩算法“365刷题计划”第72天。继续为大家讲解二分法系列篇 - 旋转排序数组最小值Ⅱ(进阶版)。话不多说,直接看题:

    程序员小浩
  • 打卡群刷题总结0727——搜索旋转排序数组 II

    链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii

    木又AI帮
  • [Leetcode][python]Sort Colors/颜色分类

    给出一个由红、白、蓝三种颜色组成的数组,把相同颜色的元素放到一起,并整体按照红、白、蓝的顺序。用0表示红色,1表示白色,2表示蓝色。这题也称为荷兰国旗问题。

    后端技术漫谈
  • 《剑指 offer》 21. 调整数组顺序使奇数位于偶数前面

    今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题 21.调整数组顺序使奇数位于偶数前面,这道题目既可以使用 首尾双指针,也可以使用 快...

    五分钟学算法
  • 【Leetcode】81. 搜索旋转排序数组 II

    ( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

    Leetcode名企之路
  • Leetcode 153. Find Minimum in Rotated Sorted Array

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan

扫码关注云+社区

领取腾讯云代金券