Binary search = half search

Time complexity O (logN)

The most standard search

1. Initialize left boundary

   int len = arr.length - 1;
   int l = 0; int r = len-1;
   

2. while loop judgment condition

   This is a left closed right closed interval (I often use it)

    while (left <= right) 
   

   There are also left closed and right open (not commonly used)

3. Get the middle coordinate mid of the interval

   int mid = l + (r - l)/2;
   // Why not write (l+r)/2?
   // because 
   int l = Integer.MAX_VALUE-1;
   int r = Integer.MAX_VALUE-1;
   // At this time, l+r will overflow
   

4. Determination of left and right boundaries

   if(nums[mid] == target){
       return mid;
   }else if(nums[mid] < target){
       l = mid+1;
   }else(target < nums[mid]){
       r = mid-1;
   }
   

Two basic principles of binary search

from 👆 so

1. Binary search should reduce the search area and reduce the left and right boundaries every time
2. The reduction method should be reasonable, and the potential answers should not be reduced

When it is known that there is a target, we can directly obtain it through size judgment and left-right boundary = mid ± 1, because there is no problem with this judgment and reduction method, but if there is a variant, the reduction method needs to be changed appropriately

Deformation 1: (known target value exists) the leftmost target value

// Finds the first element whose value is equal to the given value
private int firstEquals(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (arr[mid] < target) l = mid + 1;
        else r = mid; // Shrinking the right boundary does not affect first equals
    }
    if (arr[l] == target && (l == 0 || arr[l - 1] < target)) return l;
    return -1;
}

Deformation 2: the rightmost target value (known to exist)

// Finds the last element whose value is equal to the given value
private int lastEquals(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l < r) {
        int mid = l + ((r - l + 1) >> 1);
        if (arr[mid] > target) r = mid - 1;
        else l = mid; // Shrinking the left boundary does not affect last equals
    }
    if (arr[l] == target && (l == arr.length - 1 || arr[l + 1] > target)) return l;
    return -1;
}

Deformation 4: the first number greater than the target value

744. Find the smallest letter larger than the target letter - LeetCode (leetcode-cn.com)

public char nextGreatestLetter(char[] letters, char target) {
    int l = 0;
    int r = letters.length-1;
    if(letters[r]<=target){
        return letters[l];
    }
    while(l<r){
        int mid = l + (r-l)/2;
        if(letters[mid]<=target){
            l = mid+1;
        }else{
            r = mid;
        }
    }
    return letters[l];
}

Deformation 5: the first number greater than or equal to the target value

👇: If there is a target value, return the leftmost target value, that is, the first target value

If there is no target value, the first subscript greater than the target value is returned

If the whole array is less than the target value, num length

35. Search insertion position - LeetCode (LeetCode CN. Com)

// Finds the first element greater than or equal to the given value
public int searchInsert(int[] nums, int target) {
    int l =0;
    int r = nums.length;
    while(l<r){
        int mid = l+(r-l)/2;
        if(nums[mid]>=target){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    return l;
}

Deformation 7: the last number less than the target value

Sword finger Offer 53 - I. find the number I - LeetCode in the sorted array (LeetCode CN. Com)

Need attention! Need attention! Need attention! Need attention! 👇

Because the initial value l=0, if the whole num ≥ target, then the last l is still 0 and l=0 will not change.

That is, if(l==0) you need to judge the size relationship between num [l] and target

private int find (int[] nums,int target) {
    // The last number less than the target value
    int l =0;
    int r =nums.length-1;
    while(l<r){
        int mid = l+(r-l+1)/2;
        if(nums[mid]>=target){
            //When the intermediate value ≥ the target value, we need to reduce it because we don't need the target value, that is, r = mid -1;
            r = mid-1;
        }else{
            l = mid;
        }
    }
    return l;// If the whole num ≥ target, then l=0;
}

Deformation 3: the last number less than or equal to the target value

Case 1: if there is a target value, the last target value will be output

**Case 2: * * if there is no target value, the last number less than the target value will be output

Need attention! Need attention! Need attention! Need attention! 👇

// Finds the last element less than or equal to the given value
private int lastLessOrEquals(int[] nums, int target) {
    int l = 0;
    int r = nums.length - 1;
    while (l < r) {
        int mid = l + (r - l + 1)/2;
        if (nums[mid] > target){//I want to find elements less than or equal to target, so all elements greater than target need to be deleted
            r = mid - 1;
        } 
        else l = mid; //nums[mid] <= target 
    }
    // Note that l may not change, and a final comparison is needed 
    if (arr[l] <= target && (l == arr.length - 1 || arr[l + 1] > target)) return l; // <=
    return -1;
}