exponential_search.c

searching Implementation

43 lines
1161 bytes
C
1#include <stdio.h>
2#include <math.h>
3
4int binarySearch(int arr[], int l, int r, int x) {
5    if (r >= l) {
6        int mid = l + (r - l) / 2;
7        if (arr[mid] == x)
8            return mid;
9        if (arr[mid] > x)
10            return binarySearch(arr, l, mid - 1, x);
11        return binarySearch(arr, mid + 1, r, x);
12    }
13    return -1;
14}
15
16// Returns position of first occurrence of x in array
17int exponentialSearch(int arr[], int n, int x) {
18    // If x is present at first location itself
19    if (arr[0] == x)
20        return 0;
21
22    // Find range for binary search by repeated doubling
23    int i = 1;
24    while (i < n && arr[i] <= x)
25        i = i * 2;
26
27    // Call binary search for the found range
28    // Range is [i/2, min(i, n-1)]
29    return binarySearch(arr, i / 2, (i < n) ? i : n - 1, x);
30}
31
32int main() {
33    int arr[] = { 2, 3, 4, 10, 40, 50, 60, 70, 80, 90, 100, 120, 140, 160 };
34    int n = sizeof(arr) / sizeof(arr[0]);
35    int x = 10;
36    int result = exponentialSearch(arr, n, x);
37    if (result == -1)
38        printf("Element is not present in array\n");
39    else
40        printf("Element is present at index %d\n", result);
41    return 0;
42}
43