題目描述
給定一個排序數(shù)組和一個目標值，在數(shù)組中找到目標值私恬，并返回其索引填硕。如果目標值不在數(shù)組中麦萤，返回它將會被按順序插入的位置。
請必須使用時間復(fù)雜度為O(logn)的算法。
示例
- 示例1
輸入：nums = [1,3,5,6], target = 5
輸出：2 - 示例2
輸入：nums = [1,3,5,6], target = 2
輸出：1
方法思路
二分查找法
利用雙指針left和right频鉴，分別指向數(shù)組左邊界和右邊界栓辜。每次遍歷都重新計算中間位置mid，當目標值小于或等于nums[mid]時垛孔，right左移到mid-1位置藕甩，否則left右移到mid+1位置。如此當出現(xiàn)while(left<=right)結(jié)束條件時周荐，得到需求的位置狭莱。
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0,right = n-1,result = n;
int mid = 0;
while(left<=right){
mid = ((right-left)/2)+left;
if(target<=nums[mid]){
result = mid;
right = mid - 1;
}else{
left = mid + 1;
}
}
return result;
}
}
復(fù)雜度分析
- 時間復(fù)雜度：O(logn)，其中n為數(shù)組的長度概作。二分查找所需的時間復(fù)雜度為O(logn)腋妙。
- 空間復(fù)雜度：O(1)，我們只需要常數(shù)空間存放若干變量讯榕。
暴力破解
暴力破解法雖然不滿足時間復(fù)雜度O(logn)的條件骤素，但也是我們最易想到的。
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
for(int i=0;i<n;i++){
if(target<=nums[i]){
return i;
}
}
return n;
}
}
