0035. Search Insert Position #
题目 #
- 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
- 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
- 使用时间复杂度为
O(log n)的算法。
思路 #
二分查找（左闭右开） #
- 令右指针指向已知大于目标值的最靠前位置，左指针指向已知不大于目标值的最靠后位置
- 当两指针相遇，所指向位置为元素的插入位置
代码 #
二分查找（左闭右开） #
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int medium = left + (right - left) / 2;
if (nums[medium] == target) return medium;
else if (nums[medium] > target) right = medium;
else left = medium + 1;
}
return right;
}
}