When it comes to searching in a sorted array, Binary Search is the most commonly used method, dividing the array into two halves. But there is another interesting algorithm called Ternary Search, which divides the array into three parts instead of two. By checking two midpoints, Ternary Search can sometimes reduce the number of comparisons needed and is especially useful in scenarios like finding maximum or minimum values in unimodal functions or searching efficiently in large datasets.
with hands-on learning.
get the skills and confidence to land your next move.
Ternary Search is beginner-friendly because it extends the idea of Binary Search and demonstrates how we can divide the search space more finely to potentially save steps. Learning Ternary Search also reinforces concepts like recursion, loops, and condition-based logic in F#. For anyone starting with search algorithms, understanding Ternary Search provides deeper insight into optimizing searches beyond simple methods.
Program 1: Iterative Ternary Search
This program shows Ternary Search using a loop to iteratively divide the array into three parts and check where the key might exist.
open System
let ternarySearchIterative (arr : int[]) key =
let mutable left = 0
let mutable right = arr.Length - 1
let mutable foundIndex = -1
while left <= right && foundIndex = -1 do
let third = (right - left) / 3
let mid1 = left + third
let mid2 = right - third
if arr.[mid1] = key then
foundIndex <- mid1
elif arr.[mid2] = key then
foundIndex <- mid2
elif key < arr.[mid1] then
right <- mid1 - 1
elif key > arr.[mid2] then
left <- mid2 + 1
else
left <- mid1 + 1
right <- mid2 - 1
foundIndex
[<EntryPoint>]
let main argv =
let numbers = [| 1; 3; 5; 7; 9; 11; 13 |]
let key = 7
let result = ternarySearchIterative numbers key
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0In this approach, we calculate two midpoints and reduce the search space based on comparisons. This helps beginners understand how dividing into more parts can still efficiently locate the target.
Program 2: Recursive Ternary Search
Recursion fits naturally with Ternary Search, letting each call handle a smaller portion of the array. This program demonstrates the recursive approach.
open System
let rec ternarySearchRec (arr:int[]) key left right =
if left > right then -1
else
let third = (right - left) / 3
let mid1 = left + third
let mid2 = right - third
if arr.[mid1] = key then mid1
elif arr.[mid2] = key then mid2
elif key < arr.[mid1] then ternarySearchRec arr key left (mid1 - 1)
elif key > arr.[mid2] then ternarySearchRec arr key (mid2 + 1) right
else ternarySearchRec arr key (mid1 + 1) (mid2 - 1)
[<EntryPoint>]
let main argv =
let numbers = [| 2; 4; 6; 8; 10; 12; 14 |]
let key = 10
let result = ternarySearchRec numbers key 0 (numbers.Length - 1)
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0This recursive version helps beginners visualize how the array is repeatedly divided into three parts, and the search zone is narrowed down recursively until the key is found or the search ends.
Program 3: Ternary Search with Negative and Positive Numbers
Ternary Search works for arrays with both negative and positive numbers. As long as the array is sorted, the same logic applies.
open System
let rec ternarySearchMixed (arr:int[]) key left right =
if left > right then -1
else
let third = (right - left) / 3
let mid1 = left + third
let mid2 = right - third
if arr.[mid1] = key then mid1
elif arr.[mid2] = key then mid2
elif key < arr.[mid1] then ternarySearchMixed arr key left (mid1 - 1)
elif key > arr.[mid2] then ternarySearchMixed arr key (mid2 + 1) right
else ternarySearchMixed arr key (mid1 + 1) (mid2 - 1)
[<EntryPoint>]
let main argv =
let numbers = [| -20; -10; 0; 10; 20; 30; 40 |]
let key = -10
let result = ternarySearchMixed numbers key 0 (numbers.Length - 1)
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0By using this approach, beginners can practice with a broader range of numbers and understand that the algorithm works as long as the array is sorted.
Program 4: Ternary Search Returning Option Type
Returning an option type is more idiomatic in F#, making the result safer. This program demonstrates that.
open System
let rec ternarySearchOption (arr:int[]) key left right =
if left > right then None
else
let third = (right - left) / 3
let mid1 = left + third
let mid2 = right - third
if arr.[mid1] = key then Some mid1
elif arr.[mid2] = key then Some mid2
elif key < arr.[mid1] then ternarySearchOption arr key left (mid1 - 1)
elif key > arr.[mid2] then ternarySearchOption arr key (mid2 + 1) right
else ternarySearchOption arr key (mid1 + 1) (mid2 - 1)
[<EntryPoint>]
let main argv =
let numbers = [| 1; 2; 3; 4; 5; 6 |]
let key = 4
match ternarySearchOption numbers key 0 (numbers.Length - 1) with
| Some index -> printfn "Element %d found at index %d" key index
| None -> printfn "Element %d not found" key
0Using option types teaches beginners to handle search results safely without relying on sentinel values like -1.
Program 5: Step-by-Step Ternary Search
This program prints each midpoint checked during the search, making it easier to visualize how the array is divided into three parts.
open System
let ternarySearchStep (arr : int[]) key =
let mutable left = 0
let mutable right = arr.Length - 1
let mutable foundIndex = -1
// Loop stops naturally once we find the key
while left <= right && foundIndex = -1 do
let third = (right - left) / 3
let mid1 = left + third
let mid2 = right - third
printfn "Checking mid1=%d and mid2=%d" mid1 mid2
if arr.[mid1] = key then
foundIndex <- mid1
elif arr.[mid2] = key then
foundIndex <- mid2
elif key < arr.[mid1] then
right <- mid1 - 1
elif key > arr.[mid2] then
left <- mid2 + 1
else
left <- mid1 + 1
right <- mid2 - 1
foundIndex
[<EntryPoint>]
let main argv =
let numbers = [| 1; 3; 5; 7; 9; 11; 13 |]
let key = 11
let result = ternarySearchStep numbers key
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0Printing midpoints helps beginners understand how Ternary Search divides the array and progressively narrows the search space.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Ternary Search.
Q1. What is Ternary Search?
Ternary Search is a searching algorithm that divides a sorted array into three parts and checks two midpoints to locate a key.
Q2. Does the array need to be sorted?
Yes, Ternary Search only works on sorted arrays, similar to Binary Search.
Q3. Is Ternary Search faster than Binary Search?
Ternary Search can be slightly faster in certain scenarios, but in practice, the difference is often small. It is more of an optimization example for large datasets.
Q4. Can it handle negative numbers?
Yes, Ternary Search works with both negative and positive numbers as long as the array is sorted.
Q5. Should beginners learn Ternary Search?
Yes, it introduces advanced search logic, recursion, and how dividing the search space more finely can optimize searches.
Conclusion
Ternary Search is an advanced searching technique that divides a sorted array into three parts, checking two midpoints at a time. Through multiple F# programs, we explored iterative and recursive approaches, handling negative numbers, returning option types, and visualizing each step.
For beginners, practicing Ternary Search strengthens understanding of recursive thinking, optimized searching, and safe result handling in F#. Experimenting with different arrays and keys helps solidify the concept and prepares learners for more advanced search algorithms.
