exponential_search.c
searching Implementation
43 lines1161 bytesC
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