Algorithm description

1. Prerequisite: There are sorted arrays

2. Define the left boundary L and right boundary H, determine the search scope, and perform binary search cycle

M=Floor((L+R) /2);

4. Compare the intermediate index A[M] with the value T to be searched

  • A[M] == T indicates that the intermediate index is found
  • A[M] > T, the elements to the right of the median value are greater than T, no comparison is required, m-1 is set as the right boundary, continue to search
  • A[M] < T, the elements to the left of the median value are all less than T, no need to compare, m-1 is set as the left boundary, continue to search

LeetCode 704 questions

Algorithm implementation

public class BinarySearch {

    public static void main(String[] args) {
        int[] array = {1.5.8.11.19.22.31.35.40.45.48.49.50};
        int target = 40;
        int idx = binarySearch(array, target);
        System.out.println(idx);
        int i = recursiveBserach(array, 0, array.length - 1, target);
        System.out.println(i);
    }

    // Loop version binary search
    public static int binarySearch(int[] nums, int target) {
        int low = 0, high = nums.length - 1, mid;

        while (low <= high) {
            mid = (low + high) >>> 1;
 // mid = (low + high) /2;
            int midVal = nums[mid];
            if (midVal == target) {
                return mid;
            } else if (midVal < target) {
                low = mid + 1;
            } else {
                high = mid - 1; }}return -1;
    }
    
    /** * Recursive algorithm implements binary search **@param* nums array@paramLow left subscript *@paramHigh right subscript *@paramValue Indicates the value to be searched *@return* /
    private static int recursiveBserach(int[] nums, int low, int high, int value) {

        if (low > high) return -1;

        // find the middle subscript
        int mid = (high +low) >>> 1;

        if (nums[mid] == value) {
            return mid;

        } else if (nums[mid] > value) {
            return recursiveBserach(nums, low, mid - 1, value);
        } else {
            return recursiveBserach(nums, mid + 1, high, value); }}}Copy the code

Resolve integer overflow problems

Problem description

        int l = 0;
        int h = Integer.MAX_VALUE - 1;
        int m = (l + h) / 2;
        // The first time is ok
        System.out.println(m);
        / / on the right
        l = m+1;
        m = (l + h) / 2;
        System.out.println(m);
Copy the code

When l and r are both large, L + r may exceed the integer range, resulting in calculation errors. There are two solutions:

int m = l + (r - l) / 2;
Copy the code

There is also a case for:

int m = (l + r) >>> 1;
Copy the code

The JDK implementation

Arrays.binarySearch

 // Like public version, but without range checks.
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }
Copy the code

Binary search for common deformation

Finds the first element equal to the given value

  public static int binarySearchLeft(int[] nums, int target) {
        int low = 0, high = nums.length - 1, mid;

        while (low <= high) {
            mid = (low + high) >>> 1;
            int midVal = nums[mid];
            if (midVal == target) {
                if (mid == 0 || nums[mid - 1] != target) {
                    return mid;
                } else {
                    high = mid - 1; }}else if (midVal < target) {
                low = mid + 1;
            } else {
                high = mid - 1; }}return -1;
    }
Copy the code

Finds the last element equal to the given value

 public static int binarySearchRight(int[] nums, int target) {
        int low = 0, high = nums.length - 1, mid;

        while (low <= high) {
            mid = (low + high) >>> 1;
            int midVal = nums[mid];
            if (midVal == target) {
                if (mid == nums.length - 1 || nums[mid + 1] != target) {
                    return mid;
                } else {
                    low = mid + 1; }}else if (midVal < target) {
                low = mid + 1;
            } else {
                high = mid - 1; }}return -1;
    }
Copy the code

The first subscript greater than or equal to the target value (the target value may not exist in the array)

  public static int bsearchFirstOver(int[] nums, int target) {
        int low = 0, high = nums.length - 1, mid;

        while (low <= high) {
            mid = (low + high) >>> 1;
            int midVal = nums[mid];
            if (midVal >= target) {
                if (mid == 0 || nums[mid - 1] < target) {
                    return mid;
                } else {
                    high = mid - 1; }}else {
                low = mid + 1; }}return -1;
    }

Copy the code

The last subscript less than or equal to the target value (the target value may not exist in the array)

 public static int bsearchLastAccess(int[] nums, int target) {
        int low = 0, high = nums.length - 1, mid;

        while (low <= high) {
            mid = (low + high) >>> 1;
            int midVal = nums[mid];
            if (midVal <= target) {
                if (mid == nums.length - 1 || nums[mid + 1] > target) {
                    return mid;
                } else {
                    low = mid + 1; }}else {
                high = mid - 1; }}return -1;
    }
Copy the code