34. Search for a Range

题目：

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].

链接：https://leetcode.com/problems/search-for-a-range/#/description

4/14/2017

8ms, 53%

在找到第一个target之后，按照上行和下行分别找两个边界，代码可以refactor

 1 public class Solution {
 2     public int[] searchRange(int[] nums, int target) {
 3         int[] ret = new int[2];
 4         ret[0] = -1;
 5         ret[1] = -1;
 6         if (nums.length == 0) return ret;
 7         
 8         int lo = 0, hi = nums.length - 1;
 9         int mid;
10         while (lo <= hi) {
11             mid = lo + (hi - lo) / 2;
12             if (nums[mid] == target) {
13                 ret[0] = mid;
14                 ret[1] = mid;
15                 search(nums, target, mid + 1, hi, ret, false);
16                 search(nums, target, lo, mid - 1, ret, true);
17                 return ret;
18             } else if (nums[mid] < target) {
19                 lo = mid + 1;
20             } else {
21                 hi = mid - 1;
22             }
23         }
24         return ret;
25     }
26     
27     private void search(int[] nums, int target, int lo, int hi, int[] ret, boolean down) {
28         int mid;
29         while (lo <= hi) {
30             mid = lo + (hi - lo) / 2;
31             if (nums[mid] == target) {
32                 if (down) {
33                 if (mid < ret[0]) {
34                     ret[0] = mid;
35                 }
36                     hi = mid - 1;
37                 }
38                 else {
39                 if (mid > ret[1]) {
40                     ret[1] = mid;
41                 }
42                     lo = mid + 1;
43                 }
44             } else if (nums[mid] < target) {
45                 lo = mid + 1;
46             } else {
47                 hi = mid - 1;
48             }
49         }
50     }
51 }

我看别人都是2次binarysearch分别搞定左边和右边，并且注意下标的变化第9，20行，并且在第一轮之后i并不需要重置到0

https://discuss.leetcode.com/topic/5891/clean-iterative-solution-with-two-binary-searches-with-explanation

 1 vector<int> searchRange(int A[], int n, int target) {
 2     int i = 0, j = n - 1;
 3     vector<int> ret(2, -1);
 4     // Search for the left one
 5     while (i < j)
 6     {
 7         int mid = (i + j) /2;
 8         if (A[mid] < target) i = mid + 1;
 9         else j = mid;
10     }
11     if (A[i]!=target) return ret;
12     else ret[0] = i;
13     
14     // Search for the right one
15     j = n-1;  // We don't have to set i to 0 the second time.
16     while (i < j)
17     {
18         int mid = (i + j) /2 + 1;    // Make mid biased to the right
19         if (A[mid] > target) j = mid - 1;  
20         else i = mid;                // So that this won't make the search range stuck.
21     }
22     ret[1] = j;
23     return ret; 
24 }

divide and conquer:

https://discuss.leetcode.com/topic/16486/9-11-lines-o-log-n

 1 def searchRange(self, nums, target):
 2     def search(lo, hi):
 3         if nums[lo] == target == nums[hi]:
 4             return [lo, hi]
 5         if nums[lo] <= target <= nums[hi]:
 6             mid = (lo + hi) / 2
 7             l, r = search(lo, mid), search(mid+1, hi)
 8             return max(l, r) if -1 in l+r else [l[0], r[1]]
 9         return [-1, -1]
10     return search(0, len(nums)-1)

这个跟我的有点像，也比我好：

https://discuss.leetcode.com/topic/10692/simple-and-strict-o-logn-solution-in-java-using-recursion

4/27/2017

算法班

分别找左右边界

 1 public class Solution {
 2     /** 
 3      *@param A : an integer sorted array
 4      *@param target :  an integer to be inserted
 5      *return : a list of length 2, [index1, index2]
 6      */
 7     public int[] searchRange(int[] A, int target) {
 8         // write your code here
 9         int[] ret = new int[2];
10         ret[0] = -1;
11         ret[1] = -1;
12         if (A == null || A.length == 0) {
13             return ret;
14         }
15         
16         int start = 0, end = A.length - 1;
17         while (start + 1 < end) {
18             int mid = start + (end - start) / 2;
19             if (A[mid] >= target) {
20                 end = mid;
21             } else {
22                 start = mid;
23             }
24         }
25         if (A[start] == target) {
26             ret[0] = start;
27         } else if (A[end] == target) {
28             ret[0] = end;
29         } else {
30             return ret;
31         }
32 
33         start = ret[0];
34         end = A.length - 1;
35         while (start + 1 < end) {
36             int mid = start + (end - start) / 2;
37             if (A[mid] <= target) {
38                 start = mid;
39             } else {
40                 end = mid;
41             }
42         }
43         if (A[end] == target) {
44             ret[1] = end;
45         } else if (A[start] == target) {
46             ret[1] = start;
47         } else {
48             return ret;
49         }
50         
51         return ret;
52     }
53 }