JunyiCode
3/23/2020 - 7:07 PM

34. Find First and Last Position of Element in Sorted Array

binary search

/*
while (left <= right)   8(left) 8 10(right)
理解binary search变形能做什么
找到相同的后move towards left side to find the first same element
也可以while(target == nums[mid--])来找first same element,但是用binary search才满足o(logn)
*/

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        res[0] = findStartingIndex(nums, target);
        res[1] = findEndingIndex(nums, target);
        return res;
    }

    public int findStartingIndex(int[] nums, int target) {
        int left = 0, right = nums.length - 1, res = -1;
        
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                res = mid;
            }
            if(nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
    
    public int findEndingIndex(int[] nums, int target) {
        int left = 0, right = nums.length - 1, res = -1;
        
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                res = mid;
            }
            if(nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    } 
}