Binary Search

Binary Search is a searching algorithm for searching an element in a sorted list or array. Binary Search is efficient than Linear Search algorithm and performs the search operation in logarithmic time complexity for sorted arrays or lists.

Binary Search performs the search operation by repeatedly dividing the search interval in half. The idea is to begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Problem:

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[] using Binary Search Algorithm.

Algorithm:

We basically ignore half of the elements just after one comparison.

• Compare x with the middle element of the array.
• If x matches with the middle element, we return the mid index
• Else if x is greater than the mid element, then x can only lie in right half subarray after the mid element, so we will now look for x in only the right half ignoring the complete left half.
• Else if x is smaller, search for x in the left half ignoring the right half.

Examples:

Input: arr[] = {10, 20, 30, 40, 50, 60}, x = 20
Output: 1

Input: arr[] = {10, 15}, x = 5
Output: -1

Input: arr[] = {10, 10}, x = 10
Output o or 1

Steps:

• Compute mid = (low + high) / 2
  • Case 1: arr[mid] == x ==> return mid
  • Case 2: arr[mid] > x   ==> Repeat: high = mid - 1
  • Case 3: arr[mid] < x   ==> Repeat: low = mid + 1

Solution:

import java.util.Comparator;
import java.util.List;

/**
 * <p><b>Binary Search</b> is a searching algorithm for searching an element in a sorted
 * list or array. Binary search is efficient than Linear search algorithm and
 * performs the search operation in logarithmic time complexity for sorted lists
 * or arrays.</p>
 * <p>Binary search performs the search operation by repeatedly dividing the search interval
 * in half. The idea is to begin with an interval covering the whole array. If the value of
 * the search key is less than the item in the middle of the interval, narrow the interval
 * to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the
 * value is found or the interval is empty.</p>
 * <p><b>Time Complexity:</b> O(log n)</p>
 * <p><b>Usage:</b></p>
 * {@code
 *  BinarySearch.of(new int[]{1, 2, 3, 4, 5}, 3);
 *  String[] fruits = new String[]{"apple", "banana", "guava", "mango"};
 *  BinarySearch.of(Arrays.asList(fruits), "guava", String::compareTo)
 * }
 */
public class BinarySearch {

    /**
     * <b>Flow:</b>
     * <p><b>Iterative Implementation</b></p>
     * <p>We basically ignore half of the elements just after one comparison.</p>
     * <p>1. Compare x with the middle element of the array.</p>
     * <p>2. If x matches with the middle element, we return the mid index</p>
     * <p>3. Else if x greater than the mid element, then x can only lie in right
     * half subarray after the mid element, so we will now look for x in only
     * the right half ignoring the complete left half.</p>
     * <p>4. Else if x is smaller, search for x in the left half ignoring the
     * right half.</p>
     * <p>Compute mid = (low + high) / 2</p>
     * <p>Case 1: arr[mid] == x ===> return mid</p>
     * <p>Case 2: arr[mid] > x  ===> Repeat: high = mid - 1</p>
     * <p>Case 3: arr[mid] < x  ===> Repeat: low = mid + 1</p>
     * @param arr integer array
     * @param x element to search
     * @return index of the given element or -1 if not found
     */
    public static int of(int[] arr, int x) {
        int low = 0, high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == x)
                return mid;
            else if (arr[mid] > x)
                high = mid - 1;
            else
                low = mid + 1;
        }

        return -1;
    }

    /**
     * <b>Flow:</b>
     * <p>We basically ignore half of the elements just after one comparison.</p>
     * <p>1. Compare x with the middle element of the list.</p>
     * <p>2. If x matches with the middle element, we return the mid index</p>
     * <p>3. Else if x greater than the mid element, then x can only lie in right
     * half sublist after the mid element, so we will now look for x in only
     * the right half ignoring the complete left half.</p>
     * <p>4. Else if x is smaller, search for x in the left half ignoring the
     * right half.</p>
     * @param list type T list
     * @param key element to search
     * @param comparator comparator
     * @return index of the given element or -1 if not found
     * @param <T> type
     */
    public static <T> int of(List<? extends T> list, T key, Comparator<? super T> comparator) {
        int low = 0;
        int high = list.size() - 1;
        int index = 0;

        while (low <= high) {
            int mid = (low + high) / 2;
            int cmp = comparator.compare(key, list.get(mid));

            if (cmp == 0) {
                index = mid;
                return index;
            } else if (cmp < 0) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return index;
    }

    /**
     * <b>Flow:</b>
     * <p><b>Recursive Implementation</b></p>
     * <p>We basically ignore half of the elements just after one comparison.</p>
     * <p>1. Compare x with the middle element of the array.</p>
     * <p>2. If x matches with the middle element, we return the mid index</p>
     * <p>3. Else if x greater than the mid element, then x can only lie in right
     * half subarray after the mid element, so we will now look for x in only
     * the right half ignoring the complete left half.</p>
     * <p>4. Else if x is smaller, search for x in the left half ignoring the
     * right half.</p>
     * <p>Base case: if (low > high) return -1</p>
     * <p>Compute mid = (low + high) / 2</p>
     * <p>Case 1: arr[mid] == x ===> return mid</p>
     * <p>Case 2: arr[mid] > x  ===> search(arr, low, mid - 1, x)</p>
     * <p>Case 3: arr[mid] < x  ===> search(arr, mid + 1, high, x)</p>
     * @param arr integer array
     * @param low start index
     * @param high end index
     * @param x element to search
     * @return index of the given element or -1 if not found
     */
    public static int of(int[] arr, int low, int high, int x) {
        if (low > high) return -1;

        int mid = (low + high) / 2;

        if (arr[mid] == x)
            return mid;
        else if (arr[mid] > x)
            return search(arr, low, mid - 1, x);
        else
            return search(arr, mid + 1, high, x);
    }
}

Time Complexity: O(log n)

Auxiliary Space: O(1) for iterative solution, O(log n) for recursive solution