CS3343/3341 Analysis of Algorithms Spring 2012 |
Ternary Search
|
In "ternary" search, we are dividing the available items into three parts, rather than two. To get a number half-way between low and high, the binary search algoritm used mid = (low + high) / 2. When I first wrote the algorithm below, I wanted an integer roughly a third of the way from low to high, and I foolishly tried mid = (low + high) / 3. This is wrong, though, as you can see below. I should have realized that the midpoint is really: "start at low and go half the distance from low to high, that is mid = low + (high - low)/2. Simlarly here we must use mid = low + (high - low)/3.
| Ternary Search in Java and C | |
|---|---|
// TernarySearch.java: simple implementation
public class TernarySearch {
public int ternarySearch(int[] x, int y) {
int low = 0;
int high = x.length - 1;
while (low <= high) {
int mid = (2*low + high)/3;
if (x[mid] == y) return mid;
else if (x[mid] > y) high = mid - 1;
else {
low = mid + 1;
mid = (low + high)/2;
if (x[mid] == y) return mid;
else if (x[mid] > y) high = mid -1;
else low = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
TernarySearch tern = new TernarySearch();
int[] a =
{ 2, 8,12,14,16,19,24,28,31,33,// 0-9
39,40,45,49,51,53,54,56,57,60,// 10-19
63,69,77,82,88,89,94,96,99}; // 20-28
for (int i = 0; i < a.length; i++)
System.out.print(tern.ternarySearch(a,
a[i]) + " ");
System.out.print(tern.
ternarySearch(a,1) + " ");
System.out.print(tern.
ternarySearch(a,100) + " ");
System.out.println();
}
}
| // ternarysearch.c: simple implementation
#include <stdio.h>
int ternarySearch(int len, int x[], int y) {
int low = 0;
int high = len-1;
while (low <= high) {
int mid = (2*low + high)/3;
if (x[mid] == y) return mid;
else if (x[mid] > y) high = mid - 1;
else {
low = mid + 1;
mid = (low + high)/2;
if (x[mid] == y) return mid;
else if (x[mid] > y) high = mid -1;
else low = mid + 1;
}
}
return -1;
}
int main() {
int a[] =
{ 2, 8,12,14,16,19,24,28,31,33,// 0-9
39,40,45,49,51,53,54,56,57,60,// 10-19
63,69,77,82,88,89,94,96,99}; // 20-28
int i;
for (i = 0; i < 29; i++)
printf("%i ", ternarySearch(29, a,
a[i]));
printf("%i ", ternarySearch(29, a,1));
printf("%i ", ternarySearch(29, a,100));
printf("\n");
}
|
Common Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 -1 -1 | |