【数据结构与算法】LeetCode：二分查找

正常实现

Input : [1,2,3,4,5]
key : 3
return the index : 2

public int binarySearch(int[] nums, int key) {
    int l = 0, h = nums.length - 1;
    while (l <= h) {
        int m = l + (h - l) / 2;
        if (nums[m] == key) {
            return m;
        } else if (nums[m] > key) {
            h = m - 1;
        } else {
            l = m + 1;
        }
    }
    return -1;
}

时间复杂度

二分查找也称为折半查找，每次都能将查找区间减半，这种折半特性的算法时间复杂度为 O(logN)。

m 计算

有两种计算中值 m 的方式：

• m = (l + h) / 2
• m = l + (h - l) / 2

l + h 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围。但是 l 和 h 都为正数，因此 h - l 不会出现加法溢出问题。所以，最好使用第二种计算法方法。

未成功查找的返回值

循环退出时如果仍然没有查找到 key，那么表示查找失败。可以有两种返回值：

• -1：以一个错误码表示没有查找到 key
• l：将 key 插入到 nums 中的正确位置

变种

二分查找可以有很多变种，实现变种要注意边界值的判断。例如在一个有重复元素的数组中查找 key 的最左位置的实现如下：

public int binarySearch(int[] nums, int key) {
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int m = l + (h - l) / 2;
        if (nums[m] >= key) {
            h = m;
        } else {
            l = m + 1;
        }
    }
    return l;
}

该实现和正常实现有以下不同：

• h 的赋值表达式为 h = m
• 循环条件为 l < h
• 最后返回 l 而不是 -1

在 nums[m] >= key 的情况下，可以推导出最左 key 位于 [l, m] 区间中，这是一个闭区间。h 的赋值表达式为 h = m，因为 m 位置也可能是解。

在 h 的赋值表达式为 h = m 的情况下，如果循环条件为 l <= h，那么会出现循环无法退出的情况，因此循环条件只能是 l < h。以下演示了循环条件为 l <= h 时循环无法退出的情况：

nums = {0, 1, 2}, key = 1
l   m   h
0   1   2  nums[m] >= key
0   0   1  nums[m] < key
1   1   1  nums[m] >= key
1   1   1  nums[m] >= key
...

当循环体退出时，不表示没有查找到 key，因此最后返回的结果不应该为 -1。为了验证有没有查找到，需要在调用端判断一下返回位置上的值和 key 是否相等。

以上内容均取自：[CS-Notes](https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode 题解 - 二分查找.md)

1.X的平方根

思路

有常识可知 x 的平方根一定在 (0，x] 之间，如果暴腻一点我们可以遍历 (0,x]，分别平方寻找等于或者最近接x的那个值，但是这样做显然会消耗极大的时间 O(n)，所以我们可以采用二分查找来进行优化！

二分查找的下界为 00，上界可以粗略地设定为 xx。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 xx 的大小关系，并通过比较的结果调整上下界的范围。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码实现

class Solution {
    public int mySqrt(int x) {
        if(x <= 1) return x;
        int left = 1;
        int right = x;
        while (right >= left) {
            int mid = left + (right - left) / 2;
            int sqrt = x / mid;
            if(sqrt == mid){
                return mid;
            } else if (sqrt > mid){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
}

复杂度分析

• 时间复杂度：O(logn)，即为二分查找需要的次数。
• 空间复杂度：O(1)。

2. 寻找比目标字母大的最小字母

思路

• 方法一：采用直接遍历的方法，从左到右遍历数组，若找到一个比 target 大的字母，直接返回该字母，若没有找到，返回数组中的第一个字母。

• 方法二：采用二分查找的方法

代码实现

public char nextGreatestLetter(char[] letters, char target) {
    int len = letters.length;
    int left = 0, right = len - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (letters[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left < len ? letters[left] : letters[0];
}

复杂度分析

• 方法一：

  • 时间复杂度：O(N)
  • 空间复杂度：O(1)

• 方法二：

  • 时间复杂度：O(logN)

  • 空间复杂度：O(1)

3. 有序数组中的单一元素

思路

不难发现，数组中含有的元素总是奇数个，以为数组是由多个出现两次的元素和一个只出现一次的元素组成的。

在我们要寻找的元素之前，数组元素均成对存在；加上在该元素之后，数组成对存在的情况被改变。

我们对最中间的偶数索引 index 进行二分查找，若 index 处元素 与 index + 1 处相同，则要查找的元素在 index 右侧，反之则在 index 左侧。

依此类推继续进行二分查找，直到最后搜索区域只剩一个元素，该元素即为要查找的值。

代码实现

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            //找到中值
            int mid = left + (right - left) / 2;
            //取偶数中值
            if (mid % 2 == 1) {
                mid--;
            }
            //向右边查找
            if (nums[mid]==nums[mid + 1]) {
                left = mid + 2;
            } else {	//向左边查找
                right = mid;
            }
        }
        return nums[left];
    }
}

4. 第一个错误的版本

思路一：暴力搜索

直接遍历查找，时间复杂度为 O(n) ，调用 api 次数过多，超出题目时间限制

思路二：二分查找

如果第 m 个版本出错，则表示第一个错误的版本在 [l, m] 之间，令 h = m；否则第一个错误的版本在 [m + 1, h] 之间，令 l = m + 1。

因为 h 的赋值表达式为 h = m，因此循环条件为 l < h。

public int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

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

思路一：排序后返回数组的第一个数

将数组重新排成有序数组，那么数组的第一个值就是数组中的最小值

class Solution {
    public int findMin(int[] nums) {
        Arrays.sort(nums);
        return nums[0];
    }
}

不推荐这种做法，使用排序增加了时间复杂度。

思路二：二分查找

排序查找也就图一乐，真查找还得看二分~

public static int findMin(int[] nums) {
    int l = 0, r = nums.length - 1, mid = 0;
    while (l < r) {
        mid = l + ((r - l) >> 1);
        //这里有个编程技巧 
        //因为l<r 所以最后一轮肯定是(r,r+1)
        //那么mid 肯定是取值l 当判断条件是mid与l比时 会出现与自身比 造成出现等于情况 不好判断
        //所以判断条件时mid 与 r比 这样肯定是不同的两个数比
        if (nums[mid] < nums[r]) {  // mid可能为最小值
            r = mid;
        } else { // 没有重复值
            l = mid+1;      // mid肯定不是最小值
        }
    }
    return nums[mid];
}

6. 在排序数组中查找元素的第一个和最后一个位置

思路

可以通过二分查找寻找第一次出现的位置，最后出现的位置其实就是 target + 1 的值第一次出现的位置往前移一位

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findFirst(nums, target);
        int last = findFirst(nums, target + 1) - 1;
        if (first == nums.length || nums[first] != target) {
            return new int[]{-1, -1};
        } else {
            return new int[]{first, Math.max(first, last)};
        }
    }

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