1.题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为?
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提示:
1 <= nums.length <= 104
-104?<= nums[i] <= 104
nums?为?无重复元素?的?升序?排列数组
-104?<= target <= 104
2.核心代码???????
思路分析
在有序数组中查找，可以使用「二分查找」。
根据「题意分析」中对示例的描述：
- 情况 1：如果当前?
mid?看到的数值严格小于?target，那么?mid?以及?mid?左边的所有元素就一定不是「插入元素的位置」，因此下一轮搜索区间是?[mid + 1..right]，下一轮把?left?移动到?mid + 1?位置，因此设置?left = mid + 1；- 情况 2：否则，如果?
mid?看到的数值大于等于?target，那么?mid?可能是「插入元素的位置」，mid?的右边一定不存在「插入元素的位置」。如果?mid?的左边不存在「插入元素的位置」，我们才可以说?mid?是「插入元素的位置」。因此下一轮搜索区间是?[left..mid]，下一轮把?right?移动到?mid?位置，因此设置?right = mid。说明：上面的两点中，「情况 2」其实不用分析得那么细致， 因为只要「情况 1」的区间分析是正确的，「情况 2」一定是「情况 1」得到的区间的反面区间。
public class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
int left = 0;
int right = len;
// 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target){
// 下一轮搜索的区间是 [mid + 1..right]
left = mid + 1;
} else {
// 下一轮搜索的区间是 [left..mid]
right = mid;
}
}
return left;
}
}结合上述二分查找的方法得到下述题解
class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
int left = 0;
int right = len - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
} else if(nums[mid] > target){
right = mid - 1;
} else if(nums[mid] < target){
left = mid + 1;
} else if(left == target){
return left;
}else if(right == target) {
return right;
}
}
return left;
}
}
3.测试代码???????
class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
int left = 0;
int right = len - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
} else if(nums[mid] > target){
right = mid - 1;
} else if(nums[mid] < target){
left = mid + 1;
} else if(left == target){
return left;
}else if(right == target) {
return right;
}
}
return left;
}
}
// @solution-sync:end
class Main {
public static void main(String[] args) {
int[] nums = new int[]{1, 3, 5, 6};
int target = 5;
int result = new Solution().searchInsert(nums, target);
System.out.println(result);
}
}