Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

This article will take you through the implementation of a beautiful binary search algorithm.

Before we get to the implementation, we need to talk about the definition of binary lookup, and some of the preconditions.

The premise

The array must be ordered

Algorithm description

  1. I have an ordered array A
  2. Define the left and right boundaries of the algorithm, L and R, respectively, and perform binary search loops.
  3. Get the intermediate index M = (L + R) / 2
  4. The value of the intermediate index is compared with the value T to be looked up
  5. The value A[M] of the intermediate index is compared with the lookup value T
  6. When L > R, the loop is not found and should end

4.2a [M] = T; 4.2a [M] = T; 4.2a [M] = T; 4.3a [M] < T (M < T, M < T, M < T, M < T


Algorithm implementation

Based on the above description, we can easily implement a version of the implementation as follows:

    private static int binarySearch(int[] arr, int target){
        int left = 0, right = arr.length - 1, mid;
        while (left <= right) {
            mid = (left+ right) / 2;
            if(arr[mid] == target) {
                return mid;
            } else if(arr[mid] > target) {
                right = mid - 1;
            } else if(arr[mid] < target) {
                left = mid + 1; }}return -1;
    }
Copy the code

The above implementation looks neat and clean, but there may be some bugs

Matters needing attention

mid = (left + right) / 2; This line of code can cause overflow problems. For example, if the length of the array is the maximum value of ints and target is in the right of the middle of the array, then the first time we evaluate mid we will be ok. If left = mid + 1, then left + right will overflow.

How to solve this problem? You might often see left plus right-left over 2, and that actually works, and I’m going to write it down here. (I was shocked to see that at first.)

(left + right) / 2 ⇒ 
left / 2 + right / 2Tail + (-left /2 + right / 2Tail + (right-left) /2
Copy the code

What would I write if that was the only solution? The main thing I want to show you is the following solution, which is to divide by 2 by unsigned 1 bit to the right. (left + right) >>> 1 This is also going to divide by 2, and it’s going to be much cleaner, much more efficient.

Ok, finally post a complete and elegant implementation of dichotomy for everyone, welcome to clap bricks and discuss ha.

    private static int binarySearch(int[] arr, int target){
        int left = 0, right = arr.length - 1, mid;
        while (left <= right) {
            mid = (left+ right) >>> 1;
            if(arr[mid] == target) {
                return mid;
            } else if(arr[mid] > target) {
                right = mid - 1;
            } else if(arr[mid] < target) {
                left = mid + 1; }}return -1;
    }
Copy the code