Binary Search: flowchart, algorithm and program
This program reads n numbers that are already sorted, then looks for a key by repeatedly checking the middle element. Each check throws away half of the remaining range, so it is much faster than scanning every element.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Set found = 0.
- Step 3: Read n.
- Step 4: Set i = 0.
- Step 5: If i < n, go to step 6; otherwise go to step 8.
- Step 6: Read a[i].
- Step 7: Increase i by 1. Go to step 5.
- Step 8: Read key.
- Step 9: Set low = 0, high = n - 1.
- Step 10: If low <= high, go to step 11; otherwise go to step 18.
- Step 11: Set mid = (low + high) / 2.
- Step 12: If a[mid] == key, go to step 13; otherwise go to step 15.
- Step 13: Print position mid + 1.
- Step 14: Set found = 1. Go to step 18.
- Step 15: If key < a[mid], go to step 16; otherwise go to step 17.
- Step 16: Set high = mid - 1. Go to step 10.
- Step 17: Set low = mid + 1. Go to step 10.
- Step 18: If found == 0, go to step 19; otherwise go to step 20.
- Step 19: Print "not found".
- Step 20: Stop.
Program in C, Python and Java
Binary Search program in C
#include <stdio.h>
int main() {
int n, i, key, low, high, mid, found = 0;
int a[100];
printf("Enter n: ");
scanf("%d", &n);
printf("Enter %d sorted numbers: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
printf("Enter key: ");
scanf("%d", &key);
low = 0;
high = n - 1;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] == key) {
printf("Found at position %d\n", mid + 1);
found = 1;
break;
} else if (key < a[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if (!found) {
printf("not found\n");
}
return 0;
}Binary Search program in Python
n = int(input("Enter n: "))
a = list(map(int, input("Enter " + str(n) + " sorted numbers: ").split()))
key = int(input("Enter key: "))
low = 0
high = n - 1
found = False
while low <= high:
mid = (low + high) // 2
if a[mid] == key:
print("Found at position", mid + 1)
found = True
break
elif key < a[mid]:
high = mid - 1
else:
low = mid + 1
if not found:
print("not found")Binary Search program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n, i, key, low, high, mid;
boolean found = false;
System.out.print("Enter n: ");
n = sc.nextInt();
int[] a = new int[n];
System.out.print("Enter " + n + " sorted numbers: ");
for (i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
System.out.print("Enter key: ");
key = sc.nextInt();
low = 0;
high = n - 1;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] == key) {
System.out.println("Found at position " + (mid + 1));
found = true;
break;
} else if (key < a[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if (!found) {
System.out.println("not found");
}
}
}
Sample input: n = 5, numbers = 2 4 6 7 9, key = 7
Output: Found at position 4
How it works
- low starts at 0 and high at n - 1, so together they mark the part of the array where the key could still be.
- Inside the while (low <= high) loop, mid = (low + high) / 2 picks the middle index of that range.
- If a[mid] == key, we print mid + 1 (positions start from 1 for the user, while array indexes start from 0), set found = 1 and break.
- If key < a[mid], the key can only be on the left, so high = mid - 1. Otherwise it can only be on the right, so low = mid + 1.
- If the loop ends because low > high and found is still 0, the range is empty and we print "not found".
Dry run (trace table)
| Step | Line | Box | found | n | i | a[0] | a[1] | a[2] | a[3] | a[4] | key | low | high | mid | Output |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | |||||||||||||
| 2 | 4 | found = 0 | 0 | ||||||||||||
| 3 | 8 | Read n | 0 | 5 | |||||||||||
| 4 | 10 | i = 0 | 0 | 5 | 0 | ||||||||||
| 5 | 10 | i < n? | 0 | 5 | 0 | ||||||||||
| 6 | 11 | Read a[i] | 0 | 5 | 0 | 2 | |||||||||
| 7 | 10 | i++ | 0 | 5 | 1 | ||||||||||
| 8 | 10 | i < n? | 0 | 5 | 1 | ||||||||||
| 9 | 11 | Read a[i] | 0 | 5 | 1 | 4 | |||||||||
| 10 | 10 | i++ | 0 | 5 | 2 | ||||||||||
| 11 | 10 | i < n? | 0 | 5 | 2 | ||||||||||
| 12 | 11 | Read a[i] | 0 | 5 | 2 | 6 | |||||||||
| 13 | 10 | i++ | 0 | 5 | 3 | ||||||||||
| 14 | 10 | i < n? | 0 | 5 | 3 | ||||||||||
| 15 | 11 | Read a[i] | 0 | 5 | 3 | 7 | |||||||||
| 16 | 10 | i++ | 0 | 5 | 4 | ||||||||||
| 17 | 10 | i < n? | 0 | 5 | 4 | ||||||||||
| 18 | 11 | Read a[i] | 0 | 5 | 4 | 9 | |||||||||
| 19 | 10 | i++ | 0 | 5 | 5 | ||||||||||
| 20 | 10 | i < n? | 0 | 5 | 5 |
Time and space complexity
Time: O(n) · Space: O(1). Reading the n numbers takes O(n); the binary search itself halves the range each step, taking O(log n), and uses only a few extra variables (the array is input storage).
Common mistakes
- Using the search on an array that is not sorted. Binary search only works when the numbers are in order.
- Writing low < high instead of low <= high, which skips the case where only one element is left to check.
- Setting high = mid or low = mid instead of mid - 1 / mid + 1, which can make the loop run forever.
- Printing mid instead of mid + 1, so the position is off by one for the user.
Viva questions
Q1. What is the precondition for binary search, and what happens if the input numbers are not sorted?
The array must be sorted (here ascending). If it isn't, the decision to discard half the range is wrong, so the program may miss a key that is actually present and print 'not found'.
Q2. Why is found initialised to 0, and what is it used for?
found is a flag meaning 'key not found yet'. It becomes 1 only when a[mid] == key, so after the loop 'if (!found)' knows whether to print 'not found'.
Q3. Why are low = 0 and high = n - 1 set before the loop, and why is the loop condition low <= high rather than low < high?
Indexes run from 0 to n-1, so that is the full range at the start. Using <= keeps the case where low and high are equal, i.e. one element left, still being checked; with < that last element would be skipped.
Q4. Why do you print mid + 1 instead of mid?
mid is the array index, which starts at 0. Adding 1 gives the human position counting from 1.
Q5. What happens in the program if n is 0, or n is 1?
If n is 0, high becomes -1, so low <= high is false at once and it prints 'not found'. If n is 1, mid is 0, it compares the single element with the key and either finds it or shrinks the range to empty.
Q6. Explain what lines 24 to 28 do when the key is smaller or larger than a[mid].
If key < a[mid], the key can only be in the left half, so high = mid - 1. Otherwise it must be in the right half, so low = mid + 1. We use mid -/+ 1 because a[mid] has already been checked.
Q7. What is the time complexity of this binary search, and why? How does it compare with linear search?
O(log n), because each iteration halves the remaining range, so at most about log2(n) + 1 comparisons are needed. Linear search is O(n), so binary search is much faster on large sorted arrays. Space used is O(1).
Q8. What would change if the array contained duplicate keys, and how would you find the first occurrence?
The program reports whichever matching index mid happens to land on, not necessarily the first. To get the first occurrence, on a match record mid and set high = mid - 1 to keep searching left, instead of breaking.
Q9. Is (low + high) / 2 always safe? What could go wrong and how would you fix it?
For very large arrays low + high could overflow int. The safe form is mid = low + (high - low) / 2. With an array of at most 100 elements here it is not a problem.
Frequently asked questions
Why must the array be sorted for binary search?
Binary search decides to go left or right by comparing the key with a[mid]. That decision is only correct if smaller values are always on the left and larger values on the right.
What is the time complexity of binary search?
It is O(log n), because the range is halved on every step. For 1000 elements it needs at most about 10 comparisons, while linear search may need 1000.
Why does the program print mid + 1 instead of mid?
Array indexes start at 0, but people count positions from 1. In the sample, 7 is at index 3, so the program prints position 4.