搜索插入位置
力扣鏈接：35. 搜索插入位置 - 力扣（LeetCode）
題目
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值埂软，在數(shù)組中找到目標(biāo)值漠酿，并返回其索引沛硅。如果目標(biāo)值不存在于數(shù)組中酱鸭，返回它將會(huì)被按順序插入的位置。
請(qǐng)必須使用時(shí)間復(fù)雜度為 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 為 無(wú)重復(fù)元素 的 升序 排列數(shù)組
-104 <= target <= 104
分析
注意：排序數(shù)組
情況1：目標(biāo)值在所有數(shù)之前
情況2：目標(biāo)值在數(shù)組中
情況3：目標(biāo)值不在數(shù)組中需要插入數(shù)組中
情況4：目標(biāo)值在所有數(shù)之后
題解
暴力解法
class Solution {
public int searchInsert(int[] nums, int target) {
// 暴力解法
for(int i=0;i<nums.length;i++){ // 遍歷數(shù)組
if(nums[i]>=target){ // 如果當(dāng)前這個(gè)數(shù)大于或等于目標(biāo)值就返回索引
return i;
}
}
return nums.length; // 如果沒(méi)找到位置就插在末尾
}
}
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)
二分法
提示中說(shuō)明了nums為
無(wú)重復(fù)元素的升序排列數(shù)組 路克，可以使用二分法定義一個(gè)左閉右閉的區(qū)級(jí)[left,right]
class Solution {
public int searchInsert(int[] nums, int target) {
// 二分法 左閉右閉
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = left + ((right - left) / 2); // 尋找中間點(diǎn) 和上述二分法一樣辜荠，避免溢出
if(nums[mid] > target){
right = mid-1;
}else if(nums[mid] < target){
left = mid + 1;
}else {
return mid;
}
}
return right + 1;
}
}
時(shí)間復(fù)雜度：O(logn)
空間復(fù)雜度：O(1)
方法二
public class Solution {
public int searchInsert(int[] nums, int target) {
// 左閉右開(kāi)
int n = nums.length;
int left = 0;
int right = n;
while (left < right) {
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) { // target 在左區(qū)間
right = middle;
} else if (nums[middle] < target) { // target 在右區(qū)間殴俱，
left = middle + 1;
} else { // 數(shù)組中找到目標(biāo)值的情況政冻，直接返回下標(biāo)
return middle;
}
}
return right;
}
}
時(shí)間復(fù)雜度：O(logn)
空間復(fù)雜度：O(1)
