Binary Search

Thought Process

The Binary Search problem requires finding the index of a target element in a sorted array. Here are two approaches:

Approach 1: Iterative Binary Search - Use two pointers, start and end, to define the search range. Calculate the mid point and compare nums[mid] with the target. If nums[mid] == target, return mid. If nums[mid] > target, adjust end to mid - 1. If nums[mid] < target, adjust start to mid + 1.

Approach 2: Recursive Binary Search - Define a helper function binarySearch that takes start, end, and target as parameters. Calculate the midpoint mid and compare nums[mid] with the target. If nums[mid] == target, return mid. If nums[mid] < target, recursively search the right half. If nums[mid] > target, recursively search the left half.

Approach 1: Iterative Binary Search

class Solution {
public:
    int search(vector<int>& nums, int target) {

        int start = 0;
        int end = nums.size()-1;

        while(start<=end){

            int mid = (start+end)/2;

            if(nums[mid]==target)
                return mid;

            if(nums[mid]>target)
                end = mid-1;
            else
                start = mid+1;
        }
        return -1;
        
    }
};

Approach 2: Recursive Binary Search

class Solution {
public:
    int binarySearch(vector<int> nums,int start, int end, int target){

        int mid = (start+end)/2;

        if(start>end)
            return -1;

        if(nums[mid]==target)
            return mid;
        
        if(nums[mid]<target)
            return binarySearch(nums,mid+1,end,target);
        else
            return binarySearch(nums,start,mid-1,target);
    }
    int search(vector<int>& nums, int target) {

        int start = 0;
        int end = nums.size()-1;

        int idx = binarySearch(nums,start,end,target);
        return idx;
    }
};

Code Complexity

Time Complexity: O(log n)

Both approaches halve the search space at each step, ensuring logarithmic time complexity.

Space Complexity: O(1) for Iterative, O(log n) for Recursive

The iterative approach uses constant extra space, while the recursive approach uses stack space proportional to the depth of recursion.