Binary Search Guide: Comparing Recursive and Iterative Methods

What is Binary Search?

Binary search is a highly efficient algorithm used to locate a target value within a sorted array. By dividing the search space in half with each step, it reduces the time complexity to O(log n). In this blog, we'll explore both recursive and iterative solutions for binary search in TypeScript.

Recursive Solution

function search(nums: number[], target: number): number {
   return binarySearch(nums, target, 0, nums.length - 1);
}

function binarySearch(nums: number[], target: number, left: number, right: number): number {
    // Base case
    if (left > right) return -1;
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
        return mid;
    }
    else if (nums[mid] < target) {
        return binarySearch(nums, target, mid + 1, right);
    }
    else {
        return binarySearch(nums, target, left, mid - 1);
    }
}

How the Recursive Solution Works:

1. Function Call: search(nums, target) initializes the search by calling binarySearch with the full array bounds.

2. Base Case: If left exceeds right, the target is not in the array, so return -1.

3. Middle Index: Compute the middle index, mid = Math.floor((left + right) / 2).

4. Comparison:

   • If nums[mid] equals the target, return mid.

   • If nums[mid] is less than the target, search the right half by calling binarySearch with updated bounds.

   • If nums[mid] is greater than the target, search the left half by calling binarySearch with updated bounds.

Iterative Solution

The iterative solution uses a loop instead of recursive calls, which can be more efficient in terms of space since it avoids the overhead of multiple function calls.

function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    // Target is not found in the array
    return -1;
}

How the Iterative Solution Works:

1. Initialize Pointers: Set left to the start of the array and right to the end.

2. Loop: Continue while left is less than or equal to right.

3. Middle Index: Compute the middle index, mid = Math.floor((left + right) / 2).

4. Comparison:

   • If nums[mid] equals the target, return mid.

   • If nums[mid] is less than the target, update left to mid + 1.

   • If nums[mid] is greater than the target, update right to mid - 1.

5. Target Not Found: If the loop exits without finding the target, return -1.

Time and Space Complexity

• Time Complexity: Both recursive and iterative binary search have a time complexity of O(log n), where n is the number of elements in the array.

• Space Complexity:

  • Recursive: O(log n) due to the call stack used in recursion.

  • Iterative: O(1) as it only uses a few variables.

Comment if I have committed any mistake. Let's connect on my socials. I am always open for new opportunities , if I am free :P

Linkedin| Twitter | ShowwCase