题目描述:
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例:
题解一:
class Solution {
public int searchInsert(int[] nums, int target) {
//暴力遍历
for(int i=0;i<nums.length;i++){
if(nums[i]>=target){
return i;
}
}return nums.length;
}
}
题目思路:
- 如果数组中的值大于或者等于target,直接return
- 如果全部遍历完证明target是最大的数,直接插入末尾
题解二:
class Solution {
public int searchInsert(int[] nums, int target) {
// 二分法
int left = 0, right = nums.length - 1;
while(left <= right){
// 防止 left+right 整型溢出
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
left = mid + 1;
}else if(nums[mid] > target){
right = mid - 1;
}
}
return left;
}
}
标签:return,target,nums,int,插入,搜索,数组,leetcode35,left
From: https://www.cnblogs.com/xiaowangaixuexi/p/16916336.html