This is the 7th day of my participation in Gwen Challenge

35. Search for insertion locations

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.

The sample

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

Analysis of personal Ideas

Method one: violence

Directly traverse the number group, find the corresponding position of the target value, and return the result

class Solution {
    public int searchInsert(int[] nums, int target) {
        // go through the number group
        for (int i = 0; i < nums.length; i++) {
            // Give the corresponding judgment conditions according to the requirements
            if (nums[i] >= target){
                // When the current element is the target value or greater than the target value, the current index value is returned
                returni; }}// If all elements do not match, the target value is greater than all elements in the array
        returnnums.length; }}Copy the code

Complexity analysis

  • Time complexity:O(n)
  • Space complexity:O(1)

Submit the results

Method two: binary search

The brute force method is simple, but when the amount of data gradually increases, the corresponding execution time will greatly increase. For an ordered array, we can use binary search to optimize

class Solution {
    public int searchInsert(int[] nums, int target) {
        // Define two Pointers to the first and last part of the array
        int left = 0;
        int right = nums.length - 1;
        // Determine if the target value is greater than the last element of the array
        if (target > nums[right]){
            // If the value is greater than that, the final index value +1 is returned
            return nums.length;
        }
        // If left is greater than or equal to right, the array has been compared
        while (left < right){
            // Define an intermediate value
            int mid = left + (right - left) / 2;     
            // Determine whether the median value is equal to the target value
            if (nums[mid] == target){
                // Returns the current index value
                return mid;
            }else if(nums[mid] < target){
                // The current element is less than the target value, and the pointer moves right (the final result is the position to insert, remember +1 here)
                left = mid + 1;
            }else{
                // The pointer moves leftright = mid; }}// Returns the final remaining target index value
        returnleft; }}Copy the code

Complexity analysis

  • Time complexity:O(logn)
  • Space complexity:O(1)

Submit the results

leetcode-cn.com/problems/se…