|
目录
题目描述
思路
题解
复杂度
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:
输入: nums = [1], target = 0
输出: 0
思路
二分法 循环条件为 i<=j
最后直接返回left就可以了，根据if的判断条件，left左边的值一直保持小于target，right右边的值一直保持大于等于target，而且left最终一定等于right+1，这么一来，循环结束后，在left和right之间画一条竖线，恰好可以把数组分为两部分：left左边的部分和right右边的部分，而且left左边的部分全部小于target，并以right结尾；right右边的部分全部大于等于target，并以left为首。所以最终答案一定在left的位置。
题解
class Solution {
public int searchInsert(int[] nums, int target) {
int i=0;
int j=nums.length-1;
while(i<=j){
int mid=i+(j-i)/2;
if(nums[mid]<target){
i=mid+1;
}else if(nums[mid]>target){
j=mid-1;
}else{
return mid;
}
}
return i;
}
}
复杂度
O(logn) 时间
O1
|