binary search java implementation and time complexity

Summary

In a sorted array seq, use bisection to find v. if the range of this array is [low...high], the V we want is in this range. The way to find is to take the value from low to the middle of high. Let's suppose it is m, to compare with V. if M > V, it means that the V we want to find is in the first half of the array seq, otherwise it is in the second half. No matter in the first half or the second half, cut that part into half again and search again. Repeat the process to find where the V value is.
The implementation of binary search can use loop or recursion.

java implementation

loop

public static int iterativeSearch(int v, int[] seq) {
        int low = 0, high = seq.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            int m = seq[mid];
            if (v == m) {
                return mid;
            } else if (v > m) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

recursion

public static int recursionSearch(int v, int low, int high, int[] seq) {
        if (low > high) return -1;
        int mid = (low + high) / 2;
        int m = seq[mid];
        if (v == m) {
            return mid;
        } else if (v > m) {
            return recursionSearch(v, mid + 1, high, seq);
        } else {
            return recursionSearch(v, low, mid - 1, seq);
        }
    }
}

Java 8 native implementation

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.
    }

Time complexity

For example, there are n elements in total. The range size of each search is n, n/2, n/4 , n/2^k (the number of remaining operation elements next), where k is the number of cycles.  
Since n/2^k is rounded to > = 1, that is to say, n/2^k=1
We can get k=log2n, which is the logarithm of 2, so the time complexity can represent O()=O(logn)

Tags: Java

Posted on Tue, 31 Mar 2020 13:06:37 -0700 by shiva