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

Binary search

Given an ordered (ascending) integer array nums with n elements and a target value, write a function to search for target in NUMs, returning a subscript if the target value exists, and -1 otherwise.

  • Example 1:
  • Input: nums = [-1,0,3,5,9,12], target = 9
  • Output: 4
  • Explanation: 9 appears in NUMS with subscript 4

Dichotomy is used when an array is ordered and there are no duplicate elements in the array. The logic of dichotomy is relatively simple. The key to write dichotomy well is to define the interval clearly, and the definition of the interval is invariant. In the process of binary search, invariants should be kept, that is, every boundary processing in while search should be operated according to the definition of interval, which is the circular invariant rule. There are generally two types of interval definitions:

  • Left close right close [left, right]
  • [left, right]

Left closed right closed

Left close right close defines target in the [left, right] interval, so it has the following two points:

  • while (left <= right)Use <= becauseleft == rightMakes sense, so use <=
  • if (nums[middle] > target)Right is going to be middle-1 because the current onenums[middle]It must not be target, so the next left end index to look for is middle-1.
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1; // Define target within the range left and right, [left, right]
        while (left <= right) { // When left==right, the interval [left, right] is still valid, so <=
            int middle = left + ((right - left) / 2);// Prevent overflow equal to (left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target is in the left range, so [left, middle-1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target is in the right range, so [middle + 1, right]
            } else { // nums[middle] == target
                return middle; // Find the target value in the array, return the subscript directly}}// Target value not found
        return -1; }}Copy the code

Left closed right away

Left close, right close defines target in the [left, right) interval, which needs to be distinguished from left close, right is meaningless, so there are two points:

  • while (left < right)< is used here becauseleft == rightThe interval [left, right] is meaningless
  • if (nums[middle] > target)Right is updated to middle because the currentnums[middle]Not equal to target, go to the left interval and keep looking, and the interval is left closed and right open, so right updates to middle.This is different from closing left and closing right, ifright=middle-1Since right is meaningless, it will not be possible to compare elements in middle-1 position.
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length; // Define target within the range left and right, [left, right]
        while (left < right) { // When left==right, the interval [left, right] is still valid, so <=
            int middle = left + ((right - left) / 2);// Prevent overflow equal to (left + right)/2
            if (nums[middle] > target) {
                right = middle; // target is in the left range, so [left, middle-1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target is on the right, so [middle + 1, right]
            } else { // nums[middle] == target
                return middle; // Find the target value in the array, return the subscript directly}}// Target value not found
        return -1; }}Copy the code

Search for insertion position

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: [1,3,5,6], 5
  • Output: 2

Violent solution

Traversing the entire array in order N time

dichotomy

An ordered array with no repeating elements can be considered a dichotomy. Or divided into left closed right closed and left closed right open two. Here is the solution for closing left and closing right.

int n = nums.length;
int left = 0;
int right = n - 1; // Define target within the range left and right, [left, right]
while (left <= right) { // When left==right, the interval [left, right] is still valid
    int middle = left + ((right - left) / 2);// Prevent overflow equal to (left + right)/2
    if (nums[middle] > target) {
        right = middle - 1; // target is in the left range, so [left, middle-1]
    } else if (nums[middle] < target) {
        left = middle + 1; // target is in the right range, so [middle + 1, right]
    } else { // nums[middle] == target
        returnmiddle; }}// Handle the following four cases respectively
// Target value before all elements of array [0, -1]
Return middle;
// The target value is inserted at the position in the array [left, right], return right + 1
[left, right], return right + 1
return right + 1;
Copy the code

Other topics

Finds the first and last position of an element in a sorted array

The square root of x