Binary Search

Concept

Binary search finds a target value in a sorted array by repeatedly halving the search range. Compare the target with the middle element: if equal, found it; if target is smaller, search the left half; if larger, search the right half. Each step eliminates half the remaining elements.

When to Use

• ▸Searching for a value in a sorted array
• ▸Finding the position where a value would be inserted
• ▸Any problem where the search space can be halved each step
• ▸As a building block for binary search on answer

Intuition

Think of guessing a number between 1 and 100. The optimal strategy is always guessing the middle — the answer tells you which half to focus on. In 7 guesses you can find any number among 100. Binary search does the same on a sorted array: check the middle, go left or right, repeat. That's why it's O(log n) — you halve the problem each time.

Complexity

Template Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, target;
    cin >> n;

    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    cin >> target;

    int l = 0;
    int r = v.size()-1;

    while(l <= r){
        int mid = l + (r - l)/2;

        if(v[mid] == target){
            cout << mid;
            return 0;
        }
        else if(v[mid] < target) l = mid + 1;
        else r = mid - 1;
    }

    cout << -1;

    return 0;
}

// Sample Input:
// 10
// 1 3 5 7 9 11 13 15 17 19
// 13
//
// Sample Output:
// 6