Ternary search

#include <stdio.h>

int ternary_search(int data[], int left, int right, int search) {
  if (right - left > 0) {
    int third = (right - left) / 3;
    int first = left + third;
    int second = first + third;
    if (data[first] == search) {
        return first;
    }
    
    if (data[second] == search) {
        return second;
    }
  
    // 1 / 3  
    if (data[first] > search){
        return ternary_search(data, left, first, search);
    }
    
    // 3 / 3
    if (data[second] < search) {
        return ternary_search(data, second + 1, right, search);
    }
    
    // 2 / 3
    return ternary_search(data, first, second, search);
  }

  return -1;
}

int main() {
  int data[] = {0, 1, 5, 11, 21, 45, 70, 99};
  int left = 0;
  int right = sizeof(data) / sizeof(data[0]);
  int search = 45;

  int found = ternary_search(data, left, right, search);
  printf("%d\n", found);
  return 0;
}

$ gcc ternary.c && ./a.out
#=> 5