This is the 24th day of my participation in the August Text Challenge.More challenges in August

Tonight I am going to participate in the table tennis match, and I will do the algorithm today while I have a rest at noon. I don’t know if I will feel sleepy if I don’t take a nap. I have a feeling that a nap of 40 minutes is better, but if it lasts longer, you will wake up more tired. I don’t know whether there is a theory to explain this. Let’s continue leetcode. We’re on problem 35.

The title

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: 2

Example 2: Input: nums = [1,3,5,6], target = 2 Output: 1

Example 3: input: nums = [1,3,5,6], target = 7 output: 4

Example 4: input: nums = [1,3,5,6], target = 0 output: 0

Example 5: Input: nums = [1], target = 0 Output: 0

 

1 <= nums.length <= 10^ 4-10 ^4 <= nums[I] <= 10^4 nums is an ascending array of non-repeating elements -10^4 <= target <= 10^4

Train of thought

With today’s, that’s three consecutive days of binary search. In this case, if you do not find the binary search, you need to return the insertion position.

Another way to think of it is to return the insertion position, which is to return the smallest index greater than target. So in binary search code logic, when num[mid] > target, we need to record the current subscript mid, which is the most likely answer to the number currently iterated, because it’s greater than target, but it’s the smallest of all numbers greater than target.

Insert ans to len (len); insert ans to len (len); insert ans to len (len); insert ans to len (len)

Array = 1, 3, 5, 6, target = 2, the two black arrows are left and right, the red arrows are mid, and the numbers in the box are ANS:

Java version code

class Solution { public int searchInsert(int[] nums, int target) { int len = nums.length; Int ans = len, left = 0, right = len-1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else {// nums[mid] is the most likely answer to the current position, because it is larger than target, but it is the smallest of all the numbers larger than target. right = mid - 1; } } return ans; }}Copy the code