35 Search Insert Position 搜索插入位置
Description:
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example:
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
題目描述:
給定一個排序數(shù)組和一個目標值姊扔，在數(shù)組中找到目標值惠奸，并返回其索引。如果目標值不存在于數(shù)組中恰梢，返回它將會被按順序插入的位置佛南。
你可以假設(shè)數(shù)組中無重復元素。
示例:
示例 1:
輸入: [1,3,5,6], 5
輸出: 2
示例 2:
輸入: [1,3,5,6], 2
輸出: 1
示例 3:
輸入: [1,3,5,6], 7
輸出: 4
示例 4:
輸入: [1,3,5,6], 0
輸出: 0
思路:
由于數(shù)組已排序, 最快的方法為二分查找
時間復雜度為O(lgn), 空間復雜度為O(1)
代碼:
C++:
class Solution
{
public:
int searchInsert(vector<int>& nums, int target)
{
// return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
if (!nums.size()) return 0;
int low = 0, high = nums.size() - 1;
while (low <= high)
{
// 這里其實有l(wèi)ow/high越界的問題, 最好的方式是用無符號右移
int mid = low + ((high - low) >> 1);
if (nums[mid] >= target) high = mid - 1;
else low = mid + 1;
}
return low;
}
};
Java:
class Solution {
public int searchInsert(int[] nums, int target) {
return Arrays.binarySearch(nums, target) >= 0 ? Arrays.binarySearch(nums, target) : -(Arrays.binarySearch(nums, target) + 1);
}
}
Python:
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
# return bisect.bisect_left(nums, target)
low, high = 0, len(nums) - 1
while (low <= high):
mid = (high + low) // 2
if (nums[mid] >= target):
high = mid - 1
else:
low = mid + 1
return low
