题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
题目样例
输入: nums = [1,3,5,6], target = 5
输出: 2
输入: nums = [1,3,5,6], target = 2
输出: 1
输入: nums = [1,3,5,6], target = 7
输出: 4
输入: nums = [1,3,5,6], target = 0
输出: 0
输入: nums = [1], target = 0
输出: 0
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为无重复元素的升序排列数组
-10^4 <= target <= 10^4
Java方法:二分查找
思路及算法
用二分法考虑这个插入的位置 pos,它成立的条件为:nums[pos−1]<target≤nums[pos],其中 nums 代表排序数组。由于如果存在这个目标值,我们返回的索引也是 pos,因此我们可以将两个条件合并得出最后的目标:「在一个有序数组中找第一个大于等于 target 的下标」。
问题转化到这里,直接套用二分法即可,即不断用二分法逼近查找第一个大于等于 target 的下标。ans 初值设置为数组长度可以省略边界条件的判断,因为存在一种情况是 target 大于数组中的所有数,此时需要插入到数组长度的位置。
代码
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
执行结果
- 执行结果:通过
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:38 MB, 在所有 Java 提交中击败了66.96%的用户
复杂度
- 时间复杂度:O(log N),其中 N 是数组中的元素数量。
- 空间复杂度:O(1)。