Exponential Search is a powerful search algorithm that combines the strengths of linear and binary search. It is designed for sorted arrays and starts by finding a range where the target element may exist, exponentially increasing the index at each step. Once the potential range is located, it performs a Binary Search to find the exact position of the element. This method reduces the number of comparisons compared to simple Linear Search and is very effective for large arrays.
with hands-on learning.
get the skills and confidence to land your next move.
Exponential Search is widely used in applications that handle large datasets or where the cost of accessing array elements is uniform and significant. Learning Exponential Search in Scala not only introduces beginners to advanced search techniques but also demonstrates how combining multiple strategies can lead to efficient solutions. Understanding the algorithm helps improve programming skills and prepares learners for more complex algorithmic challenges.
Program 1: Basic Exponential Search
This program demonstrates the standard Exponential Search on a sorted integer array using a loop to find the range and Binary Search to locate the target.
object ExponentialSearchBasic {
def binarySearch(arr: Array[Int], left: Int, right: Int, target: Int): Int = {
var l = left
var r = right
while (l <= r) {
val mid = l + (r - l) / 2
if (arr(mid) == target) return mid
else if (arr(mid) < target) l = mid + 1
else r = mid - 1
}
-1
}
def exponentialSearch(arr: Array[Int], target: Int): Int = {
if (arr(0) == target) return 0
var i = 1
while (i < arr.length && arr(i) <= target) i *= 2
binarySearch(arr, i / 2, Math.min(i, arr.length - 1), target)
}
def main(args: Array[String]): Unit = {
val data = Array(1, 3, 5, 7, 9, 11, 13)
val target = 7
val index = exponentialSearch(data, target)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}This example shows how the exponential step quickly narrows the range before a Binary Search is applied. Beginners can see how combining strategies improves efficiency over linear approaches.
Program 2: Recursive Exponential Search
Here, Exponential Search is implemented recursively, highlighting the elegance of recursive thinking for range finding.
object ExponentialSearchRecursive {
def binarySearch(arr: Array[Int], left: Int, right: Int, target: Int): Int = {
if (left > right) return -1
val mid = left + (right - left) / 2
if (arr(mid) == target) mid
else if (arr(mid) < target) binarySearch(arr, mid + 1, right, target)
else binarySearch(arr, left, mid - 1, target)
}
def exponentialSearch(arr: Array[Int], target: Int, i: Int = 1): Int = {
if (arr(0) == target) return 0
if (i >= arr.length || arr(i) > target) return binarySearch(arr, i / 2, Math.min(i, arr.length - 1), target)
exponentialSearch(arr, target, i * 2)
}
def main(args: Array[String]): Unit = {
val data = Array(2, 4, 6, 8, 10, 12, 14)
val target = 10
val index = exponentialSearch(data, target)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}Recursive implementation helps beginners visualize how the search range doubles until the target is within bounds, after which Binary Search efficiently locates it.
Program 3: Exponential Search for Floating-Point Numbers
Exponential Search is not limited to integers. It can also work with sorted floating-point arrays.
object ExponentialSearchFloat {
def binarySearch(arr: Array[Double], left: Int, right: Int, target: Double): Int = {
var l = left
var r = right
while (l <= r) {
val mid = l + (r - l) / 2
if (arr(mid) == target) return mid
else if (arr(mid) < target) l = mid + 1
else r = mid - 1
}
-1
}
def exponentialSearch(arr: Array[Double], target: Double): Int = {
if (arr(0) == target) return 0
var i = 1
while (i < arr.length && arr(i) <= target) i *= 2
binarySearch(arr, i / 2, Math.min(i, arr.length - 1), target)
}
def main(args: Array[String]): Unit = {
val data = Array(1.1, 2.2, 3.3, 4.4, 5.5)
val target = 3.3
val index = exponentialSearch(data, target)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}This example shows that as long as the array is sorted, the exponential approach works for decimal values, making the algorithm versatile.
Program 4: Exponential Search with Multiple Occurrences
This program finds all positions of a target value when duplicates exist in the array.
object ExponentialSearchMultiple {
def exponentialSearchAll(arr: Array[Int], target: Int): Array[Int] = {
val n = arr.length
if (n == 0) return Array()
// Exponential search just to check existence
var i = 1
if (arr(0) == target) {
// Do not return early — duplicates may follow
} else {
while (i < n && arr(i) < target) i *= 2
val left = i / 2
val right = Math.min(i, n - 1)
// Binary search for ONE index inside the window
var found = false
var l = left
var r = right
while (l <= r && !found) {
val mid = l + (r - l) / 2
if (arr(mid) == target) found = true
if (arr(mid) < target) l = mid + 1 else r = mid - 1
}
if (!found) return Array()
}
// At this point we know the target exists somewhere.
// Now collect EVERY index in the whole array.
val out = scala.collection.mutable.ArrayBuffer[Int]()
for (k <- arr.indices) {
if (arr(k) == target) out += k
}
out.toArray
}
def main(args: Array[String]): Unit = {
val data = Array(2, 4, 4, 4, 4, 6, 8)
val target = 4
val indices = exponentialSearchAll(data, target)
if (indices.nonEmpty)
println(s"Element $target found at indices: ${indices.mkString(", ")}")
else
println(s"Element $target not found")
}
}This teaches beginners how to adapt Exponential Search to handle duplicates and collect multiple results efficiently.
Program 5: Recursive Exponential Search for Floating-Point Numbers
A recursive floating-point variant demonstrates elegance and versatility.
object ExponentialSearchFloatRecursive {
def binarySearch(arr: Array[Double], left: Int, right: Int, target: Double): Int = {
if (left > right) return -1
val mid = left + (right - left) / 2
if (arr(mid) == target) mid
else if (arr(mid) < target) binarySearch(arr, mid + 1, right, target)
else binarySearch(arr, left, mid - 1, target)
}
def exponentialSearch(arr: Array[Double], target: Double, i: Int = 1): Int = {
if (arr(0) == target) return 0
if (i >= arr.length || arr(i) > target) return binarySearch(arr, i / 2, Math.min(i, arr.length - 1), target)
exponentialSearch(arr, target, i * 2)
}
def main(args: Array[String]): Unit = {
val data = Array(1.5, 2.5, 3.5, 4.5, 5.5)
val target = 4.5
val index = exponentialSearch(data, target)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}This program reinforces how recursive Exponential Search works across different data types, helping beginners understand recursive range-finding logic.
Frequently Asked Questions (FAQ)
This section answers common questions beginners may have about Exponential Search in Scala.
Q1: What is Exponential Search?
Exponential Search is a search algorithm that finds a range where the target may exist by doubling the index, then uses Binary Search to locate it precisely.
Q2: When is Exponential Search faster than Binary Search?
It is faster when the target is near the beginning of a large array, as it quickly narrows the range.
Q3: Can Exponential Search handle floating-point numbers?
Yes, as long as the array is sorted.
Q4: Can Exponential Search find multiple occurrences?
Yes, by collecting all indices during the Binary Search step.
Q5: Why combine Exponential and Binary Search?
Exponential Search quickly identifies the probable range, and Binary Search efficiently finds the exact position, combining speed and precision.
Conclusion
Exponential Search is an efficient algorithm for searching sorted arrays by combining exponential range detection with Binary Search. Through iterative and recursive examples, for integers and floating-point numbers, and handling multiple occurrences, beginners can learn how to implement flexible and efficient search algorithms in Scala. Practicing these programs helps strengthen problem-solving skills and builds confidence in working with large datasets effectively.
