Given a sorted array of integers and a target number key
, your task is to find the first occurrence (leftmost index) of key
in the array.
If the element is not found, return -1
.
#include <stdio.h>
int solve(int n, int key, int arr[]) {
int start = 0, end = n - 1, res = -1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == key) {
res = mid;
end = mid - 1;
} else if (key < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return res;
}
int main() {
int arr[] = {5, 10, 10, 10, 20, 20};
int key = 10;
int n = sizeof(arr) / sizeof(arr[0]);
printf("First Occurrence Index: %d\n", solve(n, key, arr));
return 0;
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | The key is found at the mid index in the first iteration. |
Average Case | O(log n) | Binary search reduces the search space by half each time. |
Worst Case | O(log n) | All elements must be checked in the narrowed space to find the first occurrence. |
Comments
Loading comments...