leetcode34.Search For A Range

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

即 在一个有序排列的数组中，找到目标值所在的起始下标和结束下标。如果该目标值不在数组中，则返回[-1,-1]
题目中有一个特殊要求是时间复杂度为O(logn),也就是在暗示我们，不能只是单纯的按照顺序遍历数组，要尽量减去无效遍历。所以这题的核心思路为二分法遍历。

思路一 二分法初级运用

最初的思路是使用二分法找到目标值的其中一个下标，再根据该下标左右遍历得出初始下标和结束下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int[] searchRange(int[] nums, int target) {
    int[] result = new int[]{-1, -1};
    int left = 0;
    int right = nums.length-1;
    while(left<=right){
        int mid = (left + right)/2;
        if(nums[mid]==target){
            while(mid>=left && nums[mid]==target){
                mid--;
            }
            result[0] = mid+1;
            mid = (left + right)/2;
            while(mid<=right && nums[mid]==target){
                mid++;
            }
            result[1] = mid - 1;
            break;
        }else if (nums[mid] > target){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    return result;
}

思路二：二分法分别运用

假设我们目前有左指针，右指针，并判断中间值和目标值之间的关系，那么一共有三种关系情况

  1. 中间值小于目标值，则目标值只可能在右子数组
  2. 中间值大于目标值，则目标值只可能在左子数组
  3. 中间值等于目标值，则目标值在左右子数组都可能存在

结合情况1和情况3，当中间值小于目标值，则将左指针右移至中间，否则将右指针左移至中间。这样一定可以找到目标值的初始下标
同理，结合情况2和情况3，当中间值大于目标值，则将右指针左移至中间，否则将左指针右移至中间，这样一定可以找到目标值的结束下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int[] searchRange2(int[] nums, int target) {
    int[] range = new int[]{nums.length, -1};
    searchRange2(nums, target, 0, nums.length, range);
    if(range[0]>range[1]) range[0]=-1;
    return range;
}
public void searchRange2(int[] nums, int target, int left, int right, int[] range){
    if(left>right) return;
    int mid = ( left + right ) / 2;
    if(nums[mid] == target){
        if(mid < range[0]){
            range[0] = mid;
            searchRange2(nums, target,left, mid-1, range);
        }
        if(mid > range[1]){
            range[1] = mid;
            searchRange2(nums, target, mid+1, right, range);
        }
    }else if (nums[mid]<target){
        searchRange2(nums, target, mid+1, right, range);
    }else{
        searchRange2(nums, target, left, mid-1, range);
    }
}

这种思路更清晰的代码表示如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public int[] searchRange3(int[] nums, int target) {
    int[] result = new int[2];
    result[0] = findFirst(nums, target);
    result[1] = findLast(nums, target);
    return result;
}

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

private int findLast(int[] nums, int target){
    int idx = -1;
    int start = 0;
    int end = nums.length - 1;
    while(start <= end){
        int mid = (start + end) / 2;
        if(nums[mid] <= target){
            start = mid + 1;
        }else{
            end = mid - 1;
        }
        if(nums[mid] == target) idx = mid;
    }
    return idx;
}