三元搜索
与二分查找一样，它也将列表分成子列表。此过程使用两个中间中间值将列表分为三个部分。由于列表被划分为更多的细分，因此减少了搜索键值的时间。
三元搜索技术的复杂性
时间复杂度：O(log3n)
空间复杂度：O(1)
输入和输出
Input: A sorted list of data: 12 25 48 52 67 79 88 93 The search key 52 Output: 在以下位置找到的物品： 3
算法
ternarySearch(array, start, end, key)
输入- 一个排序的数组，开始和结束位置，以及搜索键
输出-密钥的位置（如果找到），否则位置错误。
Begin
if start <= end then
midFirst := start + (end - start) /3
midSecond := midFirst + (end - start) / 3
if array[midFirst] = key then
return midFirst
if array[midSecond] = key then
return midSecond
if key < array[midFirst] then
call ternarySearch(array, start, midFirst-1, key)
if key > array[midSecond] then
call ternarySearch(array, midFirst+1, end, key)
else
call ternarySearch(array, midFirst+1, midSecond-1, key)
else
return invalid location
End示例
#include输出结果using namespace std; int ternarySearch(int array[], int start, int end, int key) { if(start <= end) { int midFirst = (start + (end - start) /3); //第一块和第二块的中间 int midSecond = (midFirst + (end - start) /3); //第一块和第二块的中间 if(array[midFirst] == key) return midFirst; if(array[midSecond] == key) return midSecond; if(key < array[midFirst]) return ternarySearch(array, start, midFirst-1, key); if(key > array[midSecond]) return ternarySearch(array, midSecond+1, end, key); return ternarySearch(array, midFirst+1, midSecond-1, key); } return -1; } int main() { int n, searchKey, loc; cout << "输入项目数： "; cin >> n; int arr[n]; //创建一个大小为n的数组 cout << "输入项目： " << endl; for(int i = 0; i< n; i++) { cin >> arr[i]; } cout << "输入搜索键在列表中搜索： "; cin >> searchKey; if((loc = ternarySearch(arr, 0, n, searchKey)) >= 0) cout << "在以下位置找到的物品： " << loc << endl; else cout << "在列表中找不到项目。" << endl; }
输入项目数： 8 输入项目： 12 25 48 52 67 79 88 93 输入搜索键在列表中搜索： 52 在以下位置找到的物品： 3