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.

Advertisements

Pages: 1 2

3 Responses to “Ternary Search”

  1. Daniel said

    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

    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. […] looked at variants of binary search in two recent exercises. Today we look at a third […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: