Search⌘ K
AI Features
Home
Courses
Big-O Notation For Coding Interviews and Beyond

Binary Search - Recursive Implementation

Explore the recursive implementation of binary search on sorted arrays. Learn how the algorithm successively halves the search space and analyze its running time using recurrence equations and recursion depth. Understand the nuances influencing the number of recursion steps and the overall time complexity in terms accessible to beginners.

We'll cover the following...

Binary search is a well-known search algorithm that works on an already-sorted input. The basic idea is to successively eliminate half of the remaining search space at each step till either the target is found or there's no more search space left.

Binary search is recursive in nature but can also be implemented iteratively. Below is the recursive implementation of binary search.

Binary Search Implementation

Java
class Demonstration {
    public static void main( String args[] ) {
        int[] input = new int[] { 1, 3, 4, 6, 7, 101, 1009 };
        System.out.println(binarySearch(0, input.length - 1, 1009, input));
        System.out.println(binarySearch(0, input.length - 1, -1009, input));
        System.out.println(binarySearch(0, input.length - 1, 5, input));
        System.out.println(binarySearch(0, input.length - 1, 6, input));      
    }
    /**
     * start and end are inclusive indices
     *
     * @param start
     * @param end
     * @param target
     * @param input
     * @return
     */
    public static boolean binarySearch(int start, int end, int target, int[] input) {
        if (start > end) {
            return false;
        }
        int mid = (start + end) / 2;
        if (input[mid] == target) {
            return true;
        } else if (input[mid] > target) {
            return binarySearch(start, mid - 1, target, input);
        } else {
            return binarySearch(mid + 1, end, target, input);
        }
    }  
  
}

Recurrence Equation

The recurrence equation for binary search is given below:

Running Time=Cost to divide into p subproblems+p∗Cost to solve each of the p problems+Cost to merge all p problemsRunning\:Time = Cost \:to\:divide\:into\:p\:subproblems + p * Cost\:to\:solve\:each\:of\:the\:p\:problems + Cost\:to\:merge\:all\:p\:problems ...