34. 在排序数组中查找元素的第一个和最后一个位置

题目：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

思路：数组是个有序并且升序的数组，所以我们可以使用二分法来实现。有以下三种情况：
（1）target在没有在给定的数组范围内：比如，给定的数组是[3，4，5]，target为2或6，此时返回{-1， -1}；
（2）target在给定的数组范围内，但是数组中没有target：比如，数组是[3, 6，9]，target是5，此时返回{-1， -1}；
（3）target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}；

上代码：

public int[] searchRange(int[] nums, int target) {
        int index = binarySearch(nums, target);
        if (index == -1){
            return new int[]{-1, -1};
        }
        int left = index;
        int right = index;
        while (left - 1 >= 0 && nums[left - 1] == nums[index]){
            left --;
        }
        while(right + 1 < nums.length && nums[right + 1] == nums[index]){
            right ++;
        }
        return new int[]{left, right};
    }


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

        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if (nums[mid] > target){
                right = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }