Thursday, November 13, 2014

[LeetCode] Search for a Range

Given a sorted array of integers, 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].

思路:
既然要求O(log n)那必然又是binary search变种。要找到target在数组中的左右边界,必然先得要在数组中找到一个target。一种条件反射的思路是binary search找到target,即A[mid] = target,然后从mid开始向左右扫描来发现左右边界。但显然这种算法不是O(log n)的,比如当所有元素都一样,并且等于target时,算法退化为O(n)。
所以这里当A[mid] = target时,我们必须继续用二分法来查找左右边界。以下面数组为例:
4 5 8 8 8 8 9 9 10
target = A[mid=4] = 8
此时要在A[0:3]中寻找left,在A[5:8]中寻找right。
搜索left:
4 5 8 8
target != A[mid],搜索 A[mid+1 : end]。
8
target = A[mid],搜索A[start: mid-1]
start > end,left = start
搜索right:
8 9 9 10
target != A[mid],搜索A[start : mid-1]。
8
target = A[mid],搜索A[mid+1 : end]。
start > end,right = end

总结的规律就是:
二分查找时特殊处理target = A[mid]的情况
对搜索left:如果target = A[mid]则继续向左找,否则向右找。直到搜索结束,left = start
对搜索right:如果target = A[mid]则继续向右找,否则向左找。直到搜索结束,right = end
最后判断如果A[left], A[right] != target,则表明target不存在于数组中, left = right = -1


 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
39
class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> range;
        range.push_back(findLeftMost(A, n, target));
        range.push_back(findRightMost(A, n, target));
        return range;
    }
    
    int findLeftMost(int A[], int n, int target) {
        int start = 0, end = n-1;
        while(start<=end) {
            int mid = start + (end-start)/2;
            if(target<A[mid])
                end = mid-1;
            else if(target>A[mid])
                start = mid+1;
            else
                end = mid-1;
        }
        if(start>=0 && start<n && A[start]==target) return start;
        return -1;
    }
    
    int findRightMost(int A[], int n, int target) {
        int start = 0, end = n-1;
        while(start<=end) {
            int mid = start + (end-start)/2;
            if(target<A[mid])
                end = mid-1;
            else if(target>A[mid])
                start = mid+1;
            else
                start = mid+1;
        }
        if(end>=0 && end<n && A[end]==target) return end;
        return -1;
    }
};

4 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. 这个算法worst case 也是o(n)吧

    ReplyDelete
  3. findLeftMost和findRightMost可以合并成一个循环,当找到target的第一次出现的位置mid的时候,令left = mid,right = A.size()-1,继续循环即可。

    ReplyDelete
    Replies
    1. if (nums[mid] == target)
      {
      // If we haven't find the first appearance of target, and current is not the first appearance of target
      // keep going left.
      if (result.empty() && (mid > 0 && nums[mid - 1] == target)) // go left to find the first target
      {
      right = mid - 1;
      }
      else if (!result.empty() && (mid < nums.size() -1 && nums[mid + 1] == target)) // If we have found the first apperance of target, go right to find the last appearance of target
      {
      left = mid + 1;
      }
      else
      {
      result.push_back(mid);
      if (result.size() == 1)
      {
      // So now nums[mid] is the first appearance of target, now we need to find the last appearance of target.
      // rest left = mid + 1 and right to end of nums,
      left = mid;
      right = nums.size() - 1;
      }
      else
      {
      break;
      }
      }
      }

      Delete