Search a list of numbers from the start, and report how much work the search did.
What to build
A linear search that counts its own comparisons.
Requirements
- Compare the target with each number in turn, starting at index 0.
- Stop at the first match.
- Print the index of the match, or -1, and then the number of comparisons made.
Input
The first line has n. The second line has the n numbers. The third line has the target.
Output
One line: the index and the number of comparisons, separated by a space.
Constraints
1 ≤ n ≤ 100.
Example
Input:
6
72 45 90 38 66 81
66
Output:
4 5
Why it works
A linear search may have to look at every item, so its worst case is n comparisons. That is what O(n) means.
Examples
Example 1 · Input
6 72 45 90 38 66 81 66
Expected output
4 5
Example 2 · Input
4 3 1 4 1 9
Expected output
-1 4
Hints
Hint 1
Add one to a counter each time you compare an item with the target.
Hint 2
Stop the loop as soon as the target is found, so later items are not counted.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, a[100], target;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &target);
int found = -1, steps = 0;
for (int i = 0; i < n; i++) {
steps++;
if (a[i] == target) {
found = i;
break;
}
}
printf("%d %d\n", found, steps);
return 0;
}