The title

LeetCode problem 35, search for insert position association type: array

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 can assume that there are no duplicate elements in the array. Example 1: input:,3,5,6 [1], 5 output: 2 example 2: input:,3,5,6 [1], 2 output: 1 example 3: input:,3,5,6 [1], 7 output: 4 example 4: input:,3,5,6 [1], 0 output: 0Copy the code

Time to solve the problem.

class Solution {
    public int searchInsert(int[] nums, int target) {
        
        
        
    }
}

Copy the code

The method input parameters are given above to complete the answer.

Subject analysis

  1. See this problem, the first thought should be binary search
  2. But there are some critical points that you should pay attention to, such as in examples 3 and 4
  3. The search is then performed recursively

Answers to analysis

This article only analysis I do the idea, only for reference, to understand a solution to the idea, other kinds of ideas to do the problem please access the Internet.

Answer successful: Execution time :0 ms, beat 100.00% Java user memory consumption :38.2 MB, beat 45.11% Java users

class Solution { public int searchInsert(int[] nums, int target) { return binarySearch(nums, target, 0, nums.length - 1); } public int binarySearch(int[] nums, int target, int start, Int end) {if (target <= nums[start]) {return start; } else if (target > nums[start]) {return start +1; Int middle = (end-start) / 2 + start; if (nums[middle] == target) { return middle; } else if (nums[middle] > target) { return binarySearch(nums, target, start, middle - 1); } else return binarySearch(nums, target, middle + 1, end); }}}Copy the code