preface

The search insertion position of question 35 of force button is as follows:

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.

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

Tip:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 为An ascending array with no repeating elements
  • -104 <= target <= 104

A, thinking

After reading this question, there are two important information:

  • An ascending array with no repeating elements
  • Finds the location of the target value or the sequential insertion

We can classify whether the target value exists in the array as follows:

  • Target value exists: it is easy to find the target value using dichotomy
  • Target value does not exist: find the first subscript greater than the target value

If the target value does not exist, why is the first subscript greater than the target value?

Assume that nums = [1,3,5,6], target = 4, insert position 2, because nums[2] 5 is the first position greater than target = 4.

Nums [p] < target ≤ nums[p] So you just need to find the first location that is greater than or equal to Target.

For example

Nums = [1,3,5,6] and target = 4 are used as examples

P = nums.length: position of the target value, there may be all values in the array less than the target value left = 0: left boundary of the dichotomy right = nums. lengt-1: right boundary of the dichotomy

  1. mid = (left + right)/2 = 1At this time,nums[mid] < targetOn the right side.left = mid + 1 = 2
  2. mid = (left + right)/2 = 2At this time,nums[mid] > target, assignmentp = mid = 2.right = mid - 1 = 1
  3. At this timeleft > right, end the loop. Returns the result2

Second, the implementation

The implementation code

The implementation code is consistent with the idea

/** * dichotomy * keeps finding the first value greater than or equal to target */
public int searchInsert(int[] nums, int target) {
    int len = nums.length;
    int ret = len;
    int left = 0;
    int right = len -1;
    while (left <= right) {
        int mid = (left + right)/2;
        if (nums[mid] >= target) {
            ret = mid;
            right = mid - 1;
        } else {
            left = mid + 1; }}return ret;
}
Copy the code

The test code

    public static void main(String[] args) {
        int[] nums = {1.3.5.6};
        int target = 4;
        new Number35().searchInsert(nums, target);
    }
Copy the code

The results of

Third, summary

The most frustrating part of this problem is to write such important information as the ascending array of non-repeating elements into the prompt. The first time I wrote it, I also judged the ascending and descending cases. Note usually brush the topic must carefully look at the topic ah! tnt

Thank you to see the end, very honored to help you ~♥