# 0034. Find First and Last Position of Element in Sorted Array
###### tags: `Leetcode` `Medium` `Binary Search`

Binary Search的方法适合于已经有排过序的array，复杂度$O(logN)$

## 思路
这道题和普通的binary search不同的是，普通binary search只要找到这个数就好，但这题要找到最左边的这个数和最右边的这个数所在的位置。

注意binary search为了防止溢位定义mid的时候都是用```mid = start+(end-start)/2```

如果初始```end = nums.length-1```，那么在搜寻右边位置的时候，如果右边位置恰好在nums的结尾，但是由于end最大到nums.length-1，```end-=1```之后end就等于```nums.length-2```了，于是就错了
## Code

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length==0) return new int[]{-1,-1};
        int start = 0;
        int end = nums.length;
        int left, right;
        while(start<end){
            int mid = start+(end-start)/2;
            if(nums[mid]<target){
                start = mid+1;
            }
            else{
                end = mid;
            }
        }
        if(start==nums.length || nums[start]!=target){
            return new int[]{-1,-1};
        }
        left = start;
        
        start = 0;
        end = nums.length;
        while(start<end){
            int mid = start+(end-start)/2;
            if(nums[mid]<=target){
                start = mid+1;
            }
            else{
                end = mid;
            }
        }
        right = start-1;
        
        return new int[]{left, right};
    }
}

笨笨写的

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) return new int[] {-1,-1};
        int left = findLeft(nums, target);
        if (left == -1) return new int[] {-1,-1};
        int right = findRight(nums, target);
        return new int[] {left, right};
    }

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

    private int findLeft(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;
            }else {
                right = mid - 1;
            }
        }
        if (nums[left] == target) return left;
        return -1;
    }