34. Find First and Last Position in Sorted Array

问题
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

二分搜索，搜索中间项。
中间项等于左侧和右侧指针的中点，根据搜索左侧边界和右侧边界选择二分向下舍去或是二分向上补足。
当中间项小于目标，则更新左侧边界。
若中间项大于目标，则更新右侧边界。
当中间项等于目标时，根据搜索左侧边界还是右侧边界选择更新左侧或右侧。
由于有可能有重复元素存在，因此需要继续二分搜索下去，直到右侧边界大于左侧边界。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{searchLeft(nums,target),searchRight(nums,target)};
    } 

    private int searchRight(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                left = mid+1;
            }
        }
        return result;
    }
    
    private int searchLeft(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left+1)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                right = mid-1;
            }
        }
        return result;
    }
}