/*本算法是搜索來的, 稍加修飾了下, 貼出來, 以后容易找*/
/* Note:Your choice is C IDE */
#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdio>
#include <cstring>
#define N 101
using namespace std;
int partition(int arg[], int low, int high) {
int x = arg[high];
int i = low - 1;
int ex;
for(int j = low; j <= high - 1; ++ j) {
if (arg[ j ] <= x) {
i ++;
if(i == j) continue ;
ex = arg[ i ];
arg[ i ] = arg[ j ];
arg[ j ] = ex;
}
}
ex = arg[i + 1];
arg[i + 1] = arg[high];
arg[high] = ex;
return i + 1;
}
void quickSort(int arg[], int low, int high) {
if (low < high) {
int item = partition(arg, low, high);
quickSort(arg, low, item - 1);
quickSort(arg, item + 1, high);
}
}
int ternarySearch(int arg[], int x, int low, int high) {
int Fpiont;
int Spiont;
int l = high - low ;
Fpiont = (high - low) / 3 + low;
Spiont = 2 * (high - low) / 3 + low;
if(x < arg[Fpiont] && x > arg[low] && l > 3)
return ternarySearch(arg, x, low, Fpiont);
if(x < arg[Spiont] && x > arg[Fpiont] && l > 3)
return ternarySearch(arg, x, Fpiont, Spiont);
if(x > arg[Spiont] && x < arg[high] && l > 3)
return ternarySearch(arg, x, Spiont, high);
if(x == arg[Spiont]) return Spiont;
if(x == arg[Fpiont]) return Fpiont;
if(x == arg[low]) return low;
if(x == arg[high]) return high;
return -1;
}
int main() {
int input[N];
int ans, x, i;
srand( (unsigned)time( NULL ) );
//數字最好不要重復
for(i = 0; i < N; ++ i)
input[ i ] = rand() % 100 ;
sort(input, input + N);
for (i = 0; i < N; ++ i) printf("%d\t",input[ i ]);
printf("\nPlease input the number that you want to search: ");
scanf("%d",&x);
ans = ternarySearch(input, x, 0, N-1);
if(ans == -1) printf("can't find!\n");
else printf("its position is %d\n",ans + 1);
puts("finish!");
return 0;
}