ternary_search.c

searching Implementation

45 lines
1213 bytes
C
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