When working with sorted arrays, finding an element quickly is essential, especially as datasets grow larger. While Binary Search is the standard approach for efficiently searching sorted data, Ternary Search takes it a step further by dividing the array into three parts instead of two. By doing so, Ternary Search can sometimes reduce the number of comparisons in specific scenarios, making it an interesting alternative to explore.
with hands-on learning.
get the skills and confidence to land your next move.
Ternary Search is useful in situations where the array is monotonic or sorted, and the cost of comparisons is higher than simple arithmetic operations. Beginners learning Ternary Search gain insight into divide-and-conquer strategies, and it helps develop skills in breaking problems into smaller, manageable parts. Understanding this algorithm also sets the stage for more advanced search techniques in computer science.
Program 1: Iterative Ternary Search
This program demonstrates Ternary Search using a loop, searching for a number in a sorted array of integers.
Module Module1
Sub Main()
Dim data() As Integer = {2, 4, 6, 8, 10, 12, 14, 16, 18}
Dim target As Integer = 12
Dim left As Integer = 0
Dim right As Integer = data.Length - 1
Dim found As Boolean = False
While left <= right
Dim mid1 As Integer = left + (right - left) \ 3
Dim mid2 As Integer = right - (right - left) \ 3
If data(mid1) = target Then
Console.WriteLine("Element found at position: " & mid1)
found = True
Exit While
ElseIf data(mid2) = target Then
Console.WriteLine("Element found at position: " & mid2)
found = True
Exit While
ElseIf target < data(mid1) Then
right = mid1 - 1
ElseIf target > data(mid2) Then
left = mid2 + 1
Else
left = mid1 + 1
right = mid2 - 1
End If
End While
If Not found Then
Console.WriteLine("Element not found in the array.")
End If
Console.ReadLine()
End Sub
End ModuleThe array is split into three parts using two midpoints. By checking the target against these midpoints, the search area is reduced efficiently. Beginners can see how dividing into three parts requires careful adjustment of the left and right bounds for the next iteration.
Program 2: Recursive Ternary Search
This version implements Ternary Search using recursion, illustrating an alternative approach to structuring the algorithm.
Module Module1
Function TernarySearch(arr() As Integer, target As Integer, left As Integer, right As Integer) As Integer
If left > right Then Return -1
Dim mid1 As Integer = left + (right - left) \ 3
Dim mid2 As Integer = right - (right - left) \ 3
If arr(mid1) = target Then Return mid1
If arr(mid2) = target Then Return mid2
If target < arr(mid1) Then
Return TernarySearch(arr, target, left, mid1 - 1)
ElseIf target > arr(mid2) Then
Return TernarySearch(arr, target, mid2 + 1, right)
Else
Return TernarySearch(arr, target, mid1 + 1, mid2 - 1)
End If
End Function
Sub Main()
Dim data() As Integer = {1, 3, 5, 7, 9, 11, 13}
Dim target As Integer = 7
Dim result As Integer = TernarySearch(data, target, 0, data.Length - 1)
If result <> -1 Then
Console.WriteLine("Element found at position: " & result)
Else
Console.WriteLine("Element not found in the array.")
End If
Console.ReadLine()
End Sub
End ModuleThe recursive approach naturally reflects the divide-and-conquer idea of Ternary Search. Beginners can observe how the array is repeatedly divided into thirds until the target is located or the search range is exhausted.
Program 3: Ternary Search with Negative Numbers
This version shows that Ternary Search works with negative integers in a sorted array.
Module Module1
Sub Main()
Dim data() As Integer = {-30, -20, -10, 0, 10, 20, 30}
Dim target As Integer = -10
Dim left As Integer = 0
Dim right As Integer = data.Length - 1
Dim found As Boolean = False
While left <= right
Dim mid1 As Integer = left + (right - left) \ 3
Dim mid2 As Integer = right - (right - left) \ 3
If data(mid1) = target Then
Console.WriteLine("Element found at position: " & mid1)
found = True
Exit While
ElseIf data(mid2) = target Then
Console.WriteLine("Element found at position: " & mid2)
found = True
Exit While
ElseIf target < data(mid1) Then
right = mid1 - 1
ElseIf target > data(mid2) Then
left = mid2 + 1
Else
left = mid1 + 1
right = mid2 - 1
End If
End While
If Not found Then
Console.WriteLine("Element not found in the array.")
End If
Console.ReadLine()
End Sub
End ModuleThe algorithm is based purely on comparisons, so negative numbers are fully supported. Beginners learn that sorted order is the only requirement for Ternary Search to work, regardless of number sign.
Program 4: Ternary Search for Floating-Point Numbers
Ternary Search can also be applied to decimal values in sorted arrays.
Module Module1
Sub Main()
Dim data() As Double = {0.5, 1.0, 1.5, 2.0, 2.5, 3.0}
Dim target As Double = 2.0
Dim left As Integer = 0
Dim right As Integer = data.Length - 1
Dim found As Boolean = False
While left <= right
Dim mid1 As Integer = left + (right - left) \ 3
Dim mid2 As Integer = right - (right - left) \ 3
If data(mid1) = target Then
Console.WriteLine("Element found at position: " & mid1)
found = True
Exit While
ElseIf data(mid2) = target Then
Console.WriteLine("Element found at position: " & mid2)
found = True
Exit While
ElseIf target < data(mid1) Then
right = mid1 - 1
ElseIf target > data(mid2) Then
left = mid2 + 1
Else
left = mid1 + 1
right = mid2 - 1
End If
End While
If Not found Then
Console.WriteLine("Element not found in the array.")
End If
Console.ReadLine()
End Sub
End ModuleFloating-point comparisons work just like integers. Beginners can see that the algorithm adapts to different numeric types, maintaining the same divide-and-conquer logic.
Program 5: Interactive Ternary Search
This program allows users to enter a sorted array and target number, showing a practical, interactive implementation.
Module Module1
Sub Main()
Console.WriteLine("Enter sorted numbers separated by space:")
Dim input As String = Console.ReadLine()
Dim data() As Integer = Array.ConvertAll(input.Split(" "c), Function(s) Int32.Parse(s))
Console.WriteLine("Enter number to search:")
Dim target As Integer = Int32.Parse(Console.ReadLine())
Dim left As Integer = 0
Dim right As Integer = data.Length - 1
Dim found As Boolean = False
While left <= right
Dim mid1 As Integer = left + (right - left) \ 3
Dim mid2 As Integer = right - (right - left) \ 3
If data(mid1) = target Then
Console.WriteLine("Element found at position: " & mid1)
found = True
Exit While
ElseIf data(mid2) = target Then
Console.WriteLine("Element found at position: " & mid2)
found = True
Exit While
ElseIf target < data(mid1) Then
right = mid1 - 1
ElseIf target > data(mid2) Then
left = mid2 + 1
Else
left = mid1 + 1
right = mid2 - 1
End If
End While
If Not found Then
Console.WriteLine("Element not found in the array.")
End If
Console.ReadLine()
End Sub
End ModuleThis version allows experimentation with user-defined data, demonstrating how Ternary Search can be applied dynamically in real-world scenarios. Beginners can try different inputs and see how efficiently the search works compared to linear search.
Frequently Asked Questions (FAQ)
Here are some common questions beginners ask about Ternary Search:
Q1: What is the main advantage of Ternary Search?
It reduces comparisons by dividing the array into three parts instead of two, potentially lowering the number of iterations compared to Binary Search in certain scenarios.
Q2: Can Ternary Search work with negative numbers or decimals?
Yes. The array must be sorted, but negative integers and floating-point numbers are fully supported.
Q3: How is the array divided in Ternary Search?
The array is divided into three parts using two midpoints, and the search continues in the segment containing the target.
Q4: Does the array need to be sorted?
Yes. Sorted order is essential for Ternary Search to function correctly.
Q5: Is Ternary Search always faster than Binary Search?
Not always. For most practical purposes, Binary Search is slightly simpler and equally efficient. Ternary Search is mainly educational and useful in scenarios emphasizing fewer comparisons per iteration.
Conclusion
Ternary Search is a divide-and-conquer search algorithm that demonstrates how dividing a dataset into multiple parts can improve search efficiency. By exploring iterative, recursive, negative numbers, floating-point numbers, and interactive examples, beginners can understand its versatility and practical applications in VB .NET. Practicing Ternary Search strengthens algorithmic thinking and offers a deeper insight into efficient searching techniques in programming.
