Topic link

35. Search for insertion locations

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.

Note: Please use O(log n) time complexity algorithm.

The sample

  • 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
  • Example 4
// input: nums = [1,3,5,6], target = 0Copy the code
  • Example 5
// Input: nums = [1], target = 0 // output: 0Copy the code
  • Tip:
[I] <= 10⁴ nums[I] <= 10⁴ nums is an array of unrepeated elementsCopy the code

Methods to solve

Brute force

Generally speaking, there will be a brute force cracking method on the subject of the array, basically the process is as follows

  • Determine the boundary conditions of an array
  • The for loop iterates, and the target is compared to the data element in turn, and outputs the value
  • For special cases, separate judgment output is carried out

The following code

public static int searchInsert(int[] nums, int target) {
    // Determine the boundary of nums
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int n = nums.length;
    for (int i = 0; i < n ; i++) {
    // If the value of the array is greater than or equal to target, return the index of the array
        if (nums[i] >= target) {
            returni; }}// Target is greater than the last bit of the array, and returns the length of the array.
    return n;
}
Copy the code

Although the brute force cracking method is basically suitable for all array problems, but according to the problem requirements of the time complexity must be O(log N), it is obvious that the brute force cracking time complexity is O(n), we can know the use of binary search method mainly investigated.

Binary search

Binary search basically has a set of templates, and the process is as follows

  • Set left subscript left and right subscript rught
  • Through the while loop, calculate the middle table MID
  • The value between nums[mid] and target is evaluated. If nums[mid] is equal, the subscript is returned
  • Nums [mid] < target
  • Nums [mid] > target
  • At the end of the search, if there is no equivalent value, return left, which is the insertion position

The following code

public static int searchInsert(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int l = 0;
    int r = nums.length - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1; }}return l;
}
Copy the code