QUESTION 19 · Searching

What prerequisite must hold for this binary-search function?

2 marks

Answer

The array must be sorted in ascending order.

The key is compared with the middle element of the current interval.
Each unsuccessful comparison removes roughly half the remaining interval.

Explain binary search and write a non-recursive C function to implement it.

5 marks

Answer in brief

Binary search finds a key in a sorted array by repeatedly reducing a search interval to one half.

Algorithm

Set low = 0 and high = n - 1.
While low <= high, calculate mid = low + (high - low) / 2.
Return mid when a[mid] equals the key.
If the key is larger, set low = mid + 1; otherwise set high = mid - 1.
Return -1 if the interval becomes empty.

Worked trace

For 2, 4, 6, 8 and 10 with key 8, mid is initially 2 and a[2] is 6. Since 8 is larger, low becomes 3. The next midpoint is 3, whose value is 8, so index 3 is returned.

Sorted input and duplicates

The sample checks ascending order before calling the search function. Equal adjacent values are allowed. With duplicates, this version returns a matching index, which is not necessarily the first or last occurrence. Searching an unsorted array this way can miss a present key.

Time complexity

Each unsuccessful step roughly halves the candidate count: n, n/2, n/4 and so on. After about log2 n steps, at most one candidate remains. Thus worst-case search time is O(log n), while a first-midpoint match is O(1). Reading and checking the complete input is O(n), so the full interactive program has O(n) total work before and including one search.

Space complexity

This iterative function stores low, high and mid without recursive calls or another array, giving O(1) auxiliary space. The midpoint form avoids adding low and high directly.

Diagram or flowchart

Explain binary search and write a non-recursive C function to implement it. · Download diagram

C program and output

Download .c Open compiler

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
int binary_search(const int a[], int n, int key)
{
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key) { return mid; }
        if (a[mid] < key) { low = mid + 1; }
        else { high = mid - 1; }
    }
    return -1;
}

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    for (int i = 1; i < n; ++i) {
        if (a[i] < a[i - 1]) { puts("Array must be sorted"); return 1; }
    }
    int key;
    if (scanf("%d", &key) != 1) { puts("Unsupported input"); return 1; }
    printf("Index = %d\n", binary_search(a, n, key));
    return 0;
}

Sample input and output

Input

5
2 4 6 8 10
8

Output

Index = 3

Worked example: a key that is absent

Take the sorted array 3, 8, 12, 17, 21, 29, 34 and search for 20. Indexes begin at zero. Count one visit each time the algorithm examines a midpoint element; a visit can include more than one C comparison.

↔ Scroll horizontally on a small screen

Binary search for 20
Visit	low	high	mid	Element	Next step
1	0	6	3	17	20 is larger: low becomes 4
2	4	6	5	29	20 is smaller: high becomes 4
3	4	4	4	21	20 is smaller: high becomes 3

Now low = 4 and high = 3. No candidate remains, so the function returns -1. It examined only three midpoint elements. The key need not lie outside the array’s smallest and largest values to be absent.

Common mistake: leaving the midpoint in the interval

Suppose the only remaining element is 21 and the key is 20. Setting high = mid leaves the same interval unchanged. The next iteration can examine 21 again forever. Use high = mid - 1, because the midpoint has already been ruled out. The same reasoning gives low = mid + 1 for the other branch.

Boundary cases

With one element, a matching key returns index 0; a different key returns -1.
The search function can accept n = 0 and return -1 without reading an element. The interactive driver on this page deliberately accepts only 1–20 elements.
With 4, 4, 4, the current function can return index 1. It does not promise the first occurrence.