Find First and Last Position of Element in Sorted Array_34

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

image.png

（图片来源https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

）

Notice:

1. 细节，需要debug查看

两步：

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

        int[] res = new int[]{-1, -1};
        int l = 0, r = nums.length-1;
        while(l+1 < r) {
            int m = l + (r-l)/2;
            if(nums[m] == target) {
                r = m;
            } else if(nums[m] < target) {
                l = m;
            } else {
                r = m;
            }
        }

        if(nums[l] == target) {
            res[0] = l;
        } else if(nums[r] == target) {
            res[0] = r;
        }

        l = 0; 
        r = nums.length-1;
        while(l+1 < r) {
            int m = l + (r-l)/2;
            if(nums[m] == target) {
                l = m;
            } else if(nums[m] < target) {
                l = m;
            } else {
                r = m;
            }
        }

        if(nums[r] == target) {
            res[1] = r;
        } else if(nums[l] == target) {
            res[1] = l;
        }

        return res;
    }

一步

public int[] searchRange(int[] nums, int target) {
        int[] res = {-1, -1};
        if(nums == null || nums.length <= 0) {
            return res;
        }

        int lo = 0, hi = nums.length - 1;

        //lo is the start index of target
        //hi is the end index of target
        while(nums[lo] < nums[hi]) {    //  非lo<hi，保证了nums[lo]、nums[hi]最多只有一个是target
            int mid = lo + (hi - lo)/2;
            if(nums[mid] > target) {  // target is in the left half
                hi = mid - 1;
            } else if(nums[mid] < target) {  // target is in the right half
                lo = mid + 1;
            } else {  // find target, then need to find the start and end point
                if(nums[lo] != nums[mid]) { // 此时，target一定在lo的右边
                    lo++;
                } else {  // nums[lo]、nums[hi]最多只有一个是target。既然nums[lo]==target，那么target一定在hi的左边
                    hi--;
                }
            }
        }

        //check whether find the target number
        if(nums[lo] == nums[hi] && nums[lo]== target) {
            res[0] = lo;
            res[1] = hi;
        }

        return res;
    }