This is the fourth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

Topic describes

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. The sample1: Input: nums = [1.3.5.6], target = 5Output:2The sample2: Input: nums = [1.3.5.6], target = 2Output:1The sample3: Input: nums = [1.3.5.6], target = 7Output:4The sample4: Input: nums = [1.3.5.6], target = 0Output:0The sample5: Input: nums = [1], target = 0Output:0Tip:1 <= nums.length <= 104
-104 <= nums[i] <= 104Nums is an ascending array of non-repeating elements -104 <= target <= 104Source: LeetCode//leetcode-cn.com/problems/search-insert-positionCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Ideas & CODE

1. Cycle of violence

Even though they say the time has to be order logn, let’s try the cycle of violence.

Ideas:

  • Through the array
  • If the current element> =Target value, since the array is ordered, simply return the current index
  • If all the elements are<Target value, then return the maximum index plus one.

The code is as follows:

public int searchInsert(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] >= target) {
            returni; }}return nums.length;
}
Copy the code

2. The dichotomy

When you see time order logn, the first thing that comes to mind is binary.

Binary search as long as you haven’t done it for a while, you forget all about it, and here’s a simple summary.

The idea of reduction and cure

To reduce: to reduce the problem

Z: It means solving problems

When we divide a problem into subproblems, we look for the answer in only one of them, which is the idea of subtraction.

Application scenarios

  • Find a number in an ordered array (binary subscript)

Key words: array, order

The value is for arrays because arrays are indexed, which allows quick access to elements

  • Find an integer in the integer range (binary answer)

If we are looking for an integer and we know the range of the integer, we can use a binary search algorithm to gradually narrow down the range of the integer

Subject train of thought

Let’s start with the code:

public int searchInsert(int[] nums, int target) {
    int len = nums.length;
    // Special judgment
    if (nums[len - 1] < target) {
        return len;
    }
    int left = 0;
    int right = len - 1;
    // The result of the loop must be left==right
    while (left < right) {
        // The median value is not written as (left+right)/2
        int mid = left + (right - left) / 2;
        // Target must be greater than or equal to the previous value
        if (nums[mid] < target) {
            // Next interval [mid+1, right]
            left = mid + 1;
        } else {
            // next interval [left, mid]right = mid; }}return left;
}
Copy the code
  • Why is itwhile (left < right)Rather thanwhile (left <= right)?

While (left < right) breaks out of the loop if left==right, and left and right are the same. This situation is usually used for complex binary searches and will not return in the loop.

While (left <= right) breaks out of the loop with the condition left > right, that is, left == right will loop again, so generally in this case, the loop will return according to the condition, for simple binary search.

  • Why is itint mid = left + (right - left) / 2;Rather thanint mid = (left + right) / 2;

To prevent the two ints from getting too large, they add up and overflow

  • How does the interval change with each cycle?

Mainly through the description of the topic, to determine the next cycle of the left and right boundaries and the opening and closing of the boundary