题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
O(log n)的算法。示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
解题思路
使用二分查找寻找target，如果target存在就返回它在数组中的下标，如果它不存在就返回它的插入位置，我们只需要不停的对比mid的元素大小和target的关系，如果当前mid对应的元素已经大于target，就令right = mid - 1，往更小的区间找；如果当前mid对应的元素小于target,就令left = mid + 1, 往更大的区间找；如果当前mid对应元素已经和target相等，则直接返回mid；当退出循环后，说明target不在数组中，但当前left指向的位置即为要插入的位置
代码实现
class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else {return mid;}}return left;}
}