【算法100天 | 3】筑基二分查找（含LeetCode 34题 在排序数组中查找元素的第一个和最后一个位置）

1、在排序数组中某个数是否存在

思路：

最直观的思路是直接从前往后遍历一遍，但是并没有利用到数组升序排列的条件；
由于数组已经排序、整个数组是单调递增的，我们可以利用二分法来加速查找的过程；

代码：

// arr是有序的，num是目标数
public boolean find(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return false;
    }
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == num) {
            return true;
        } else if (arr[mid] < num) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

2、 在有序数组中找到第一个大于等于某个数的数

思路：

采用二分查找，每次判断中间数mid是否 大于等于 目标数num，如果是则令ans 等于 mid、右边界R 等于 mid-1，否者令左边界L等于mid + 1，直到 L > R。

代码：

// arr是有序的，找到>=num 最小的数
public int nearLeftIndex(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int L = 0;
    int R = arr.length - 1;
    int ans = -1;
    while (L <= R) {
        int mid = L + ((R - L) >> 1);
        if (arr[mid] >= num) {
            ans = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    return ans;
}

3、在有序数组中找到最后一个小于等于某个数的数

思路：

思路和在有序数组中找到第一个大于等于某个数的数相似。

代码：

// arr是有序的，找到<=num 最大的数
public static int nearRightIndex(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int L = 0;
    int R = arr.length - 1;
    int ans = -1;
    while (L <= R) {
        int mid = L + ((R - L) >> 1);
        if (arr[mid] <= num) {
            ans = mid;
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }
    return ans;
}

4、在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）

1）题干和示例

2）方法一：一次二分查找 + 遍历

1> 思路

先采用二分查找法从有序数组中找到一个target，然后再从找到的这个target数向两边开始遍历，直到数组中相应位置的数不是target；不过极端场景下，有可能会变成O(n)的时间复杂度。

2> 代码

public int[] searchRange(int[] nums, int target) {
    if (nums == null || nums.length < 1) {
        return new int[]{-1, -1};
    }
    int left = 0;
    int right = nums.length - 1;

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

3）方法二：两次二分查找

1> 思路

使用两次二分查找：一次返回第一个大于等于target的下标leftIndex，一次返回第一个大于target的下标rightIndex。由于target可能不存在数组中，所以需要在返回前校验这两个下标leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target。

这里可以选择写两个二分查找的函数；不过为了优雅，可以只写一个函数，用一个标识lower来表明是哪种情况。

2> 代码

public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length < 1) {
            return new int[]{-1, -1};
        }
        int leftIndex = binarySearch(nums, target, true);
        int rightIndex = binarySearch(nums, target, false) - 1;
        if (leftIndex <= rightIndex && rightIndex < nums.length && nums[leftIndex] == nums[rightIndex]) {
            return new int[]{leftIndex, rightIndex};
        }
        return new int[]{-1, -1};
    }

    private int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0;
        int right = nums.length - 1;
        int ans = nums.length;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            // 或前面的逻辑为：返回第一个大约target的下标，后面的逻辑为：返回第一个大于等于target的下标
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }