Skip to lab content

UNIT 05 · Sorting and Searching

Binary search with a non-recursive function

EXERCISE 05BC173 sample runs

THE SYLLABUS QUESTION

What you need to solve

Write a C program that uses a non-recursive function to search for a Key value in a given sorted list of integers using binary search method.
Input format & conventions

Array size n (1–100), then n integers in non-decreasing order (-1,000,000 to 1,000,000), then the key. A matching 1-based position is returned; when duplicates exist, it need not be the first.

UNDERSTAND THE IDEA

Explanation

Compare the key with the middle value. If it is smaller, keep the left half; if larger, keep the right half.

The search function is iterative, not recursive. It uses low + (high - low) / 2 for the midpoint. main checks that the input is sorted rather than silently sorting or accepting invalid input.

PLAN BEFORE CODING

Algorithm

  1. Read and verify the sorted list and key.
  2. Initialize low = 0 and high = n - 1.
  3. Compare the key with the middle element.
  4. Return on equality; otherwise reduce the search interval.
  5. Stop when low > high and return -1.

SEE THE CONTROL FLOW

Flowchart

Follow the arrows from Start. Diamonds ask a question; labeled arrows show the answer. A returning arrow repeats a loop. Function internals are grouped where needed; later input checks follow the rules in the program.

Flowchart for Binary search with a non-recursive function: input, decisions, processing, output and loop paths

On a phone, scroll sideways to read the diagram at full size. Open full-size flowchart ↗

C17

Complete C program

Download .c
#include <stdio.h>
#define MAX_SIZE 100

int readArray(int a[], int *n) {
    if (scanf("%d", n) != 1 || *n < 1 || *n > MAX_SIZE) return 0;
    for (int i = 0; i < *n; ++i)
        if (scanf("%d", &a[i]) != 1 || a[i] < -1000000 || a[i] > 1000000) return 0;
    return 1;
}

int binarySearch(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 (key < a[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

int main(void) {
    int a[MAX_SIZE], n, key;
    if (!readArray(a, &n) || scanf("%d", &key) != 1) {
        puts("Invalid input."); return 1;
    }
    for (int i = 1; i < n; ++i) {
        if (a[i] < a[i - 1]) { puts("Input must be sorted in ascending order."); return 1; }
    }
    int index = binarySearch(a, n, key);
    printf("Position: %d\n", index < 0 ? -1 : index + 1);
    return 0;
}
Open in compiler ↗

Code loads into the existing compiler. Enter the sample input there; sign-in and execution rules stay the same.

Compile and run locally
gcc -std=c17 binary-search.c -o lab
./lab

On Windows, run .\lab.exe after compiling with GCC. The interest program requires the math library where applicable.

FOLLOW THE VALUES

Dry run

Step / stateOperationResult
Array 2,4,6,8,10; key 8low = 0; high = 4; mid = 26 < 8: move low to 3
low = 3; high = 4mid = 38 matches
Display index + 1Found at index 3Position 4

CHECK THE BEHAVIOR

Sample input & output

Each output below was produced by compiling and running this exact program. Input values are entered in the stated order; the examples do not print input prompts.

Sample 1

INPUT 
5
2 4 6 8 10
8
OUTPUT
Position: 4

Sample 2

INPUT 
4
1 3 5 7
2
OUTPUT
Position: -1

Sample 3

INPUT 
1
9
9
OUTPUT
Position: 1

Common mistakes

  • Binary search needs sorted input.
  • Move past the midpoint (mid + 1 or mid - 1) to ensure progress.

WHY THIS GROWTH RATE?

Time and space complexity

Search O(log n); sorted-input validation O(n), so the complete program is O(n). O(1) additional search space.

At each comparison, binary search discards about half the remaining interval: n, n/2, n/4, and so on. After k reductions, about n / 2^k elements remain. Setting this to 1 gives k ≈ log2 n, so the search is O(log n) in the worst case and O(1) if the first midpoint matches.

This complete program reads the entire array and verifies that it is sorted. Both steps take O(n), so total time is O(n) + O(log n) = O(n). For example, searching 1,024 already sorted values takes at most 11 midpoint checks, but validating them still requires a linear scan.

The non-recursive search keeps only low, high and mid, giving O(1) extra search space. The input array itself uses O(n) storage.

Big-O describes how work grows as the stated input quantity grows; fixed factors and lower-order terms are omitted. The analysis treats fixed-width arithmetic as constant cost and the published limits as practical safety bounds.