二分查找------查找区间

1. 题目

2. 思路和题解

这道题虽然是道中等题，并且看起来很复杂，但是实际上就是给定一个数组和目标值，让我们去寻找该目标值在数组中的位置。题目还提到说设计O(log n)的算法解决问题，更进一步暗示我们去用二分查找。要找开始位置和结束位置，那就分两步：

1. 寻找开始位置

while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        arr[0] = mid; //找到目标值后，将下标赋值给数组第一个元素
        right = mid - 1; // 这一步很重要，是为了寻找在这之前，是否还存在目标值
    } else if (nums[mid] < target){
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

2. 寻找结束位置

while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        arr[1] = mid;
        left = mid + 1; //这一步和上面一样也很重要，是为了确定在这之后，是否还存在目标值
    } else if (nums[mid] < target){
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

所以整体代码如下

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int[] arr = {-1, -1};
        //第一次查找
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                arr[0] = mid;
                right = mid - 1;
            } else if (nums[mid] < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        //第二次查找
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                arr[1] = mid;
                left = mid + 1;
            } else if (nums[mid] < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return arr;
    }
}