34. Search for a Range

 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 }

 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 }

 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)