[LeetCode 34] Find First and Las

Solution

1. 需要找数组中给定target的一个范围，如图，需要找8在数组中的起止index

   
   image.png
2. 由于题目要求的Time Complexity O(log N),那么肯定是二分法。
3. 二分法的基本原则，根据middle与target的比较决定如何移动start & end。

if  target < middle, move end ==> end = middle
if target > middle, move start ==> start = middle

4. 但本题的关键在于出现了重复，需要找重复target的startIndex and endIndex, 那么现在问题是当target == middle时，怎么找First & Last Position?? 需要区分找StartIndex 和EndIndex
   1). 找StartIndex时，move end pointer ==> end = middle
   2). 找EndIndex时，move start pointer ==> start = middle

二分法的链接
https://blog.csdn.net/int64ago/article/details/7425727/

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        
        if (nums == null || nums.length == 0)
            return result;
        
        //1. search for first position
        int start = 0;
        int end = nums.length - 1;
        
        while (start + 1 < end) {
            int middle = start + (end - start) / 2;
            
            if (target <= nums[middle]) {
                end = middle;
            } else {
                start = middle;
            }
        }
        
        // cannot find the target
        if (nums[start] != target && nums[end] != target )
            return result;
        
        //求的是first postion，所以先找start，找不到再找end
        if (nums[start] == target) {
            result[0] = start;
        } else {
            result [0] = end;
        }
        
        //2. search for last postion
        start = 0;
        end = nums.length - 1;
        
        while (start + 1 < end) {
            int middle = start + (end - start) / 2;
            
            if (target >= nums [middle]) {
                start = middle;
            } else {
                end = middle;
            }
        }
        
        //求的是last postion，所以先找end，找不到再找start
        if (nums[end] == target) {
            result[1] = end;
        } else {
            result[1] = start;
        }
        
        return result;
    }
}