搜索插入位置（二分法实现）

题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 注意：你可以假设数组中无重复元素。

示例 : 输入: [1,3,5,6], 5 输出: 2

注意点

1、数组有序，所以可以使用二分法实现； 2、使用二分法时要注意边界的考虑，和是否查找了所有元素。

使用了left = 0、right = nums.length - 1，则循环条件必须为left <= right，因为left和right都必须取到 [left, right]，所以当left = right时还需要继续判断；使用了left = 0、right = nums.length，则循环条件必须为left < right，因为left必须取到，而right不用取到 [left, right)，所以当left = right时不需要继续判断。

实现

public int searchInsert(int[] nums, int target) { //数组为null或者target小于nums[0]时，直接返回0 if(nums == null || nums[0] >= target) return 0; int left = 0; int right = nums.length - 1; while(left <= right){ int mid = left + (right - left) / 2; if(nums[mid] == target){ //存在目标元素，直接返回下标 return mid; }else if(nums[mid] < target){ left = mid + 1; }else if(nums[mid] > target){ right = mid - 1; } } //不存在，返回插入位置（退出循环时，left = nums.length） return left; }