คืออะไร?
คล้าย Binary Search แต่แบ่งรายการเป็น 3 ส่วน ด้วย 2 Mid Values ลดเวลาค้นหาลงเพราะแบ่งย่อยมากกว่า
Complexity
- Time: O(log₃ n)
- Space: O(1)
Input/Output
Input: Sorted: 12 25 48 52 67 79 88 93 Key: 52 Output: Item found at location: 3
อัลกอริทึม
ternarySearch(array, start, end, key):
if start <= end:
midFirst = start + (end - start) / 3
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)
else: return ternarySearch(array, midFirst+1, midSecond-1, key)
else: return invalid
โค้ด C++ และ Output
// ternarySearch function recursive // main: input n, array, searchKey, call ternarySearch
Enter number of items: 8 Enter items: 12 25 48 52 67 79 88 93 Enter search key: 52 Item found at location: 3
