给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
自己想到的解法,时间复杂度为 O(n)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| let length = nums.length;
if (target <= nums[0]) {
return 0;
} else if (target === nums[length - 1]) {
return length - 1;
} else if (target > nums[length - 1]) {
return length;
} else {
let flag = false;
for (let i = 0; i < nums.length; i++) {
if (target === nums[i]) return i;
else flag = true;
}
if (flag) {
for (let i = 0; i < nums.length; i++) {
if (target >= nums[i] && target <= nums[i + 1]) {
return i + 1;
}
}
}
}
|
经过 gpt 改进后的代码,时间复杂度为 O(log n)，划重点：看到已排序的数组，就要想到二分查找法！记住此代码模板！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| function searchInsert(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
|
力扣高赞解题
注意：
二分查找的思路不难理解，但是边界条件容易出错，比如 循环结束条件中 left 和 right 的关系，更新 left 和 right 位置时要不要加 1 减 1。