题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

解题思路

1. 对数组只存在一个元素的特殊情况进行单独判断；
2. 设置变量控制左右边界，通过取中间值比较大小来缩小范围，避免遍历数组所有值；

代码展示

class Solution {public int searchInsert(int[] nums, int target) {if(nums.length == 1){if(nums[0] == target){return 0;} else if (nums[0] < target){return 1;} else {return 0;}}int left = 0;int right = nums.length - 1;int middle = 0;while (left < right){if(left + 1 == right){if(nums[left] == target){return left;} else if(nums[right] < target){return right + 1;} else if (nums[left] > target) {return Math.max(0, left - 1);} else {return right;}} else {middle = (left + right) / 2;if(nums[middle] == target){return middle;} else if (nums[middle] > target){right = middle;} else {left = middle;}}}return middle + 1;}
}