Search a sorted list by halving it, and count how few steps that takes.
What to build
A binary search that reports the number of times it looked at a middle item.
Requirements
- Start with
lo = 0andhi = n - 1, and usemid = (lo + hi) / 2. - Count one step each time you compare
a[mid]with the target. - For each target, print its index, or -1, and then the number of steps.
Input
The first line has n. The second line has n different numbers in increasing order. The third line has q, and the fourth has the q targets.
Output
One line for each target: the index and the number of steps.
Constraints
1 ≤ n ≤ 100 and 1 ≤ q ≤ 100.
Example
Input:
7
1 3 5 7 9 11 13
4
7 1 13 4
Output:
3 1
0 3
6 3
-1 3
Why it works
Every step throws away half of what is left, so 16 numbers need at most 5 steps and a million need about 20. That is O(log n).
Examples
7 1 3 5 7 9 11 13 4 7 1 13 4
3 1 0 3 6 3 -1 3
1 10 2 10 5
0 1 -1 1
Hints
Hint 1
Keep two indexes, lo and hi, that mark the part of the array still to search.
Hint 2
Each time round the loop, work out mid, count one step, and compare a[mid] with the target.
Hint 3
If a[mid] is too small, the answer is to the right: lo = mid + 1. Otherwise hi = mid - 1.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, q, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &q);
for (int k = 0; k < q; k++) {
int target;
scanf("%d", &target);
int lo = 0, hi = n - 1, found = -1, steps = 0;
while (lo <= hi) {
int mid = (lo + hi) / 2;
steps++;
if (a[mid] == target) {
found = mid;
break;
}
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d %d\n", found, steps);
}
return 0;
}