LeetCode 34 - Search for a Range

https://leetcode.com/problems/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].

X. https://discuss.leetcode.com/topic/6327/a-very-simple-java-solution-with-only-one-binary-search-algorithm

 public int[] searchRange(int[] A, int target) {
  int start = Solution.firstGreaterEqual(A, target);
  if (start == A.length || A[start] != target) {
   return new int[]{-1, -1};
  }
  return new int[]{start, Solution.firstGreaterEqual(A, target + 1) - 1};
 }

 //find the first number that is greater than or equal to target.
 //could return A.length if target is greater than A[A.length-1].
 //actually this is the same as lower_bound in C++ STL.
 private static int firstGreaterEqual(int[] A, int target) {
  int low = 0, high = A.length;
  while (low < high) {
   int mid = low + ((high - low) >> 1);
   //low <= mid < high
   if (A[mid] < target) {
    low = mid + 1;
   } else {
    //should not be mid-1 when A[mid]==target.
    //could be mid even if A[mid]>target because mid<high.
    high = mid;
   }
  }
  return low;
 }

//方法一，采用[]闭区间的方式

private static int firstGreaterEqual2(int[] A, int target) {
    int low = 0, high = A.length - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        // low <= mid < high
        if (A[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low;
}

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

X.
http://blog.csdn.net/happyaaaaaaaaaaa/article/details/50846000

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

1.     public int[] searchRange(int[] nums, int target) {  
2.         int[] res = new int[2];  
3.         res[0] = bSearchLeft(nums, target, 0, nums.length-1);  
4.         res[1] = bSearchRight(nums, target, 0, nums.length-1);  
5.         return res;  
6.     }  
7.     private int bSearchLeft(int[] nums, int target, int left, int right) {  
8.         if(left > right) return (left < nums.length && nums[left] == target) ? left : -1;  
9.         int mid = (left + right) / 2;  
10.         if(nums[mid] < target) return bSearchLeft(nums, target, mid+1, right);  
11.         else return bSearchLeft(nums, target, left, mid - 1);  
12.     }  
13.     private int bSearchRight(int[] nums, int target, int left, int right) {  
14.         if(left > right) return (right >= 0 && nums[right] == target) ? right : -1;  
15.         int mid = (left + right) / 2;  
16.         if(nums[mid] > target) return bSearchRight(nums, target, left, mid-1);  
17.         else return bSearchRight(nums, target, mid+1, right);  
18.     }  

https://all4win78.wordpress.com/2016/09/02/leetcode-34-search-for-a-range/

    public int[] searchRange(int[] nums, int target) {

        int[] result = {-1, -1};

        if (nums == null || nums.length == 0) {

            return result;

        }

        int start = 0;

        int end = nums.length - 1;

        result[0] = findLeft(nums, 0, end, target);

        if (result[0] != -1) {

            result[1] = findRight(nums, result[0], end, target);

        }

        return result;

    }

     

    private int findLeft(int[] nums, int start, int end, int target) {

        while (start != end) {

            int mid = (end - start) / 2 + start;

            if (nums[mid] >= target) {

                end = mid;

            } else {

                start = mid + 1;

            }

        }

        return (nums[start] == target) ? start : -1;

    }

     

    private int findRight(int[] nums, int start, int end, int target) {

        while (start != end) { // scary

            int mid = (end - start) / 2 + start + 1;

            if (nums[mid] == target) {

                start = mid;

            } else {

                end = mid - 1;

            }

        }

        return start;

    }

https://discuss.leetcode.com/topic/21783/easy-java-o-logn-solution

public int[] searchRange(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;
}

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

    public int[] searchRange(int[] A, int target) {
        int[] range = {A.length, -1};
        searchRange(A, target, 0, A.length - 1, range);
        if (range[0] > range[1]) range[0] = -1; 
        return range;
    }
    
    public void searchRange(int[] A, int target, int left, int right, int[] range) {
        if (left > right) return;
        int mid = left + (right - left) / 2;
        if (A[mid] == target) {
            if (mid < range[0]) {
                range[0] = mid;
                searchRange(A, target, left, mid - 1, range);
            }
            if (mid > range[1]) {
                range[1] = mid;
                searchRange(A, target, mid + 1, right, range);
            }
        } else if (A[mid] < target) {
            searchRange(A, target, mid + 1, right, range);
        } else {
            searchRange(A, target, left, mid - 1, range);
        }
    }

X. Inefficient
http://www.programcreek.com/2014/04/leetcode-search-for-a-range-java/

public int[] searchRange(int[] nums, int target) {
    if(nums == null || nums.length == 0){
        return null;
    }
 
    int[] arr= new int[2];
    arr[0]=-1;
    arr[1]=-1;
 
    binarySearch(nums, 0, nums.length-1, target, arr);
 
    return arr;
}
 
public void binarySearch(int[] nums, int left, int right, int target, int[] arr){
    if(right<left) 
        return;
 
    if(nums[left]==nums[right] && nums[left]==target){
        arr[0]=left;
        arr[1]=right;
        return;
    }
 
    int mid = left+(right-left)/2;
 
 
    if(nums[mid]<target){
        binarySearch(nums, mid+1, right, target, arr);
    }else if(nums[mid]>target){
        binarySearch(nums, left, mid-1, target, arr);
    }else{
        arr[0]=mid;
        arr[1]=mid;
 
        //handle duplicates - left
        int t1 = mid;
        while(t1 >left && nums[t1]==nums[t1-1]){
            t1--;
            arr[0]=t1;
        }
 
        //handle duplicates - right
        int t2 = mid;
        while(t2 < right&& nums[t2]==nums[t2+1]){
            t2++;
            arr[1]=t2;
        }
        return;
    }
}

http://www.bijishequ.com/detail/134759?p=66

说是找区间，这道题其实本质上就是找第一个和最后一个target出现的位置。方法就是：找到target保存到range数组之后继续在剩余区间内查找，如果又发现了target就更新下标。因为要不断向高低两个方向搜索，所以要用两个Binary Search。（当然也可以用分治的思想，以类似MergeSort为框架，不断merge区间的位置，但本文主要讲Binary Search，所以就不细说了）

public int[] searchRange(int[] nums, int target) {
int[] range = new int[]{ -1, -1 };
if (nums.length == 0) {
return range;
}

// 1.Find first occurence of target
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] < target) {
low = mid + 1;
} else if (nums[mid] > target) {
high = mid - 1;
} else {
range[0] = mid;
high = mid - 1; // find target, but continue binary search on [low,mid)
}
}

if (range[0] == -1) {
return range;
}

// 2.Find last occurence of target
low = 0; high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] < target) {
low = mid + 1;
} else if (nums[mid] > target) {
high = mid - 1;
} else {
range[1] = mid;
low = mid + 1; // find target, but continue binary search on (mid,high]
}
}
return range;
}