“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
[B] [C] [D]
Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order.
You must use an O(log n) time complexity algorithm.
Example 1:
Input: nums = [1,3,5,6], target = 5 output: 2Copy the code
Example 2:
Input: nums = [1,3,5,6], target = 2 Output: 1Copy the code
Example 3:
Input: nums = [1,3,5,6], target = 7 output: 4Copy the code
Example 4:
Input: nums = [1,3,5,6], target = 0 output: 0Copy the code
Example 5:
Input: nums = [1], target = 0 Output: 0Copy the code
Tip:
1 <= nums.length <= 104
nums
为Non-repeating elementtheascendingArrangement of array-104 <= target <= 104
Let’s just find the first place that is greater than or equal to the target value.
For this kind of problem, the natural idea is to use binary search to solve the problem
Binary search
Binary lookup applies to finding the first place in an ordered array that matches the condition
The overall method is to compare the middle value of the search interval with the target value each time, judge whether the target value is in the first half or the second half of the current interval through the size relationship, and then adjust the interval to the corresponding part, so that the search interval is halved each time until the element or position that meets the conditions is found
At this point, our problem solution idea is complete, the following is the code implementation
var searchInsert = function(nums, target) {
if(target<nums[0]) return 0;
if(target>nums[nums.length-1]) return nums.length;
let l = 0,r = nums.length-1;
while(l<r){
const mid = (l+r)>>1;
if(nums[mid]<target) l = mid+1
else r = mid;
}
return l;
};
Copy the code
At this point, we are done with Leetcode-35 – searching for the insertion location
If you have any questions or suggestions, please leave a comment!