BinarySearch in JAVA

When given a sorted list of numbers, binary search is the best algorithm to have in your arsenal. The binary search finds the target element in O(log(n)) time by taking advantage of the sorted property of the list. The algorithm starts with two pointers, the first and the last elements of the list, and compares the middle element against the target. If the middle element matches the target, the algorithm stops and returns true. Assuming the list is sorted in ascending order. If the middle element is less than the target, the left pointer gets moved to one element to the right of the middle pointer, effectively halving the range of the search space. The same efficiency is achieved on the right half of the list when the middle element is greater than the target.

Example

#   0   1   2   3   4   5   6   7   8   idx
#   2   4   6   9   17  18  19  22  23  target = 18
#   i               m               j   0 + (8 - 0)/2 = 4
#                       18  19  22  23
#                       i   m       j   5 + (8 - 5)/2 = 6
#                       18
#                       imj             5 + (5 - 5)/2 = 5
#   done because [m] = target
#   return true

Implementation

public static boolean binarySearch(int[] arr, int target) {
    int n = arr.length, i = 0, j = n - 1;

    while (i <= j) {
        int m = i + (j - i) / 2;
        if (arr[m] == target)
            return true;
        else if (arr[m] < target)
            i = m + 1;
        else
            j = m - 1;
    }

    return false;
}

Variants

This article is my 21st oldest. It is 235 words long, and it’s got 0 comments for now.