Binary search

Halve it every time

In a sorted array, look at the middle element. If it's your value, done. If it's too small, the value can only be in the right half; too big, the left half. Repeat on that half.

Each step halves what's left, so a million elements take about 20 steps instead of a million.

Keep lo and hi as the range still possible, and compute mid = lo + (hi - lo) / 2.

Exercise: Binary search

Read n (1 to 100000), n numbers in increasing order (all different), then q queries. For each query value print its position (0-based), or -1 if it isn't there. Use binary search.

Break it: Break the binary search

This binary search should print Found or Missing. Find an input where it's wrong.

#include <stdio.h>

int main() {
    int n, x, a[20];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &x);
    int lo = 0, hi = n - 1, found = 0;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == x) found = 1;
        if (a[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    printf(found ? "Found\n" : "Missing\n");
    return 0;
}

Input rules: first line n (1 to 20), second line n increasing whole numbers between -1000 and 1000, third line the value to look for.