Binary Search

Binary Search Implementation (Iterative and Recursive)

Rajeev SinghAlgorithms1 mins read

Binary Search

Given a sorted array of of n elements, find if a given element target is present in the array.

Binary search is the most efficient algorithm for searching an element in a sorted array. It has a run-time complexity of O(log n).

In this article, you’ll find both iterative and recursive implementation of binary search in Java.

Binary Search Implementation (Iterative)

Binary search begins by comparing the middle element of the array to the target value.

  • If the target value is equal to the middle element, its position in the array is returned.
  • If the target value is less than the middle element, then we continue the search in the lower half of the array.
  • If the target value is greater than the middle element, then we continue the search in the upper half of the array.

By doing this, the algorithm repeatedly divides the search space in half, thereby achieving a time-complexity of O(log n)

Let’s look at the iterative implementation of binary search:

import java.util.Scanner;

class BinarySearch {
    private static int binarySearch(int[] a, int target) {
        int start = 0;
        int end = a.length-1;

        while(start <= end) {
            int mid = (start + end)/2;

            if(target == a[mid]) {
                return mid;
            } else if (target < a[mid]) {
                end = mid-1;
            } else {
                start = mid+1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
          a[i] = keyboard.nextInt(); 
        }
        int target = keyboard.nextInt();
        keyboard.close();

        System.out.printf("BinarySearch(%d) = %d%n", target, binarySearch(a, 0, n-1, target));
    }
}

Binary Search Implementation (Recursive)

The following example shows how to implement the binary search recursively.

class BinarySearch {
    private static int binarySearchRecursive(int[] a, int start, int end, int target) {
        if (start > end) {
            return -1;
        }
        int mid = (start + end)/2;

        if(target == a[mid]) {
            return mid;
        } else if (target < a[mid]) {
            return binarySearchRecursive(a, start, mid-1, target);
        } else {
            return binarySearchRecursive(a, mid+1, end, target);
        }
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
          a[i] = keyboard.nextInt(); 
        }
        int target = keyboard.nextInt();
        keyboard.close();

        System.out.printf("BinarySearch(%d) = %d%n", target, binarySearchRecursive(a, 0, n-1, target));
    }
}