What is Binary Search?

Binary Search is a divide-and-conquer algorithm that searches for a target value in a sorted array by repeatedly dividing the search space in half. Unlike linear search which checks every element, binary search eliminates half of the remaining elements in each step.

Key Prerequisites:

• The array must be sorted (ascending or descending)
• Random access to elements (works well with arrays)

Algorithm Steps:

1. Find the middle element of the array
2. Compare the middle element with the target value
3. If they match, return the index
4. If target is smaller, search the left half
5. If target is larger, search the right half
6. Repeat until found or search space is empty

Code:

int search(vector<int>& nums, int target) {
    int s = 0;
    int e = nums.size() - 1;
    
    while (s <= e) {
        int mid = s + (e - s) / 2;
        
        if (nums[mid] == target) {
            return nums[mid];
        } else if (target > nums[mid]) {
            s = mid + 1;
        } else {
            e = mid - 1;
        }
    }
    
    return -1;
}

Time Complexity Analysis

Derivation of Time Complexity :

Step 1: Understanding the problem size

• Initial array size: n