Ternary Search

November 10, 2017

We looked at binary search in the previous exercise. Today we look at ternary search. Instead of one mid at the middle of the array, ternary search has two mids a third of the way from each end; two-thirds of the array is discarded at each recursive step.

Your task is to write a program that performs ternary search. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
3 Comments »

3 Responses to “Ternary Search”

  1. Daniel said
    November 10, 2017 at 2:31 PM

    Here’s a solution in C99.

    /* ternary_search.c */

#include <stdio.h>

int search(int* array, int n, int element) {
  int lo = 0;
  int hi = n;
  while (hi > lo) {
    int addend = (hi - lo) / 3;
    int mid1 = lo + addend;
    int val1 = array[mid1];
    int mid2 = mid1 + addend;
    int val2 = array[mid2];
    if (val1 == element) return mid1;
    if (val2 == element) return mid2;
    if (val1 > element) {
      hi = mid1;
    } else if (val2 < element) {
      lo = mid2 + 1;
    } else {
      lo = mid1 + 1;
      hi = mid2;
    }
  }
  return -1;
}

int main(void) {
  int array[] = {0,1,2,4,7,8,9,10,11,12,13,15,17,18,19};
  int n = sizeof(array) / sizeof(int);
  printf("element: index\n");
  for (int i = 0; i < 20; ++i) {
    int idx = search(array, n, i);
    printf("%d: %2d\n", i, idx);
  }
}

    Build:

    $ c99 -Wall -o ternary_search ternary_search.c

    Output:

    element: index
0:  0
1:  1
2:  2
3: -1
4:  3
5: -1
6: -1
7:  4
8:  5
9:  6
10:  7
11:  8
12:  9
13: 10
14: -1
15: 11
16: -1
17: 12
18: 13
19: 14
  2. Paul said
    November 11, 2017 at 10:23 AM

    Like in the Python bisect module I have implemented a trisect_left, which finds an insert point for x. If x is already in the array the new x will be inserted at the left. Then tsearch_left will use trisect_left and find x, if it is there.

    def trisect_left(arr, x):
    'find insert point for x - if x is already in the array, insert left'
    n = len(arr)
    lo, hi = 0, n
    while lo < hi:
        delta = (hi - lo) // 3
        i1 = lo + delta
        if arr[i1] < x:
            lo = i1 + 1
        else:
            hi = i1
            continue
        i2 = hi - delta
        if arr[i2] < x:
            lo = i2 + 1
        else:
            hi = i2
    return lo

def tsearch_left(arr, x):
    i = trisect_left(arr, x)
    if i != len(arr) and arr[i] == x:
        return i
    return -1
  3. Floor And Ceiling In An Array | Programming Praxis said
    November 21, 2017 at 10:01 AM

    […] looked at variants of binary search in two recent exercises. Today we look at a third […]

Leave a comment