ternary_search.c
searching Implementation
45 lines1213 bytesC
1#include <stdio.h>
2
3// A recursive ternary search function. It returns location of x in
4// given array arr[l..r] is present, otherwise -1
5int ternarySearch(int l, int r, int x, int arr[]) {
6 if (r >= l) {
7 int mid1 = l + (r - l) / 3;
8 int mid2 = r - (r - l) / 3;
9
10 // If x is present at the mid1
11 if (arr[mid1] == x)
12 return mid1;
13
14 // If x is present at the mid2
15 if (arr[mid2] == x)
16 return mid2;
17
18 // If x is present in left one-third
19 if (arr[mid1] > x)
20 return ternarySearch(l, mid1 - 1, x, arr);
21
22 // If x is present in right one-third
23 if (arr[mid2] < x)
24 return ternarySearch(mid2 + 1, r, x, arr);
25
26 // If x is present in middle one-third
27 return ternarySearch(mid1 + 1, mid2 - 1, x, arr);
28 }
29
30 // We reach here when element is not present in array
31 return -1;
32}
33
34int main() {
35 int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
36 int l = 0;
37 int r = 9;
38 int x = 5;
39 int result = ternarySearch(l, r, x, arr);
40 if (result == -1)
41 printf("Element is not present in array\n");
42 else
43 printf("Element is present at index %d\n", result);
44}
45