二分查找规范

二分查找主要用来判断有序数组中是否存在某个目标元素。

但是有的时候我们需要知道该目标元素在数组中出现的位置信息，这就带来了两个问题：

• 寻找目标数字在有序数组中首次出现的位置
• 寻找目标数字在有序数组中最后一次出现的位置

另外，可能有的时候还需要知道目标数字不存在的时候，它应该插入到有序数组的哪个位置，这种情况我们会约定负数作为索引下标。

二分搜索首次出现的位置

public int getFirstIndex(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;
        }
    }
    if (left<nums.length && nums[left]==target){
        return left;
    }else {
        return -left;
    }
}

nums[mid]>=target 的时候，使 right = mid-1，表示尽可能的使 right 往左移动。

当存在目标数字时，返回 left 和 right+1 是等效的。

二分搜索最后一次出现的位置

public int getLastIndex(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;
        }
    }
    if (right>=0 && nums[right]==target){
        return right;
    }else {
        return -left;
    }
}

nums[mid]<=target 的时候，使 left = mid+1，表示尽可能的使 left 往右移动。

当存在目标数字时，返回 right 和 left-1 是等效的。