Exponential Search Algorithm
The Exponential Search Algorithm, also known as Exponential Binary Search, is an efficient search algorithm designed for searching a sorted array or list. It is a variation of the binary search algorithm that allows for faster searching by reducing the search space significantly. The key idea behind exponential search is to find a range within which the desired element lies and then apply binary search to that range. This range is determined by repeatedly expanding the search interval by powers of 2 until the target value is found to be within the interval or until the end of the array is reached.
The algorithm begins by searching for the initial range by comparing the target value with the first element of the array. If the target value is equal to the first element, the search is successful, and the index is returned. If the target value is greater than the first element, the algorithm proceeds by comparing the target value with the element at index 2^i, where i starts at 1 and is incremented in each iteration. Once an element greater than or equal to the target value is found or the end of the array is reached, the algorithm narrows down the search range by performing a binary search between the previous index (2^(i-1)) and the current index (2^i). The binary search will then return the index of the target value if it exists within the array or indicate that the value is not present in the array.
package ExponentialSearch
import (
"math/rand"
"testing"
"time"
)
func ExponentialSearch(array []int, number int) int {
boundValue := 1
for boundValue < len(array) && array[boundValue] < number {
boundValue *= 2
}
if boundValue > len(array) {
boundValue = len(array) - 1
}
return BinarySearch(array, boundValue+1, number)
}
func BinarySearch(array []int, bound, number int) int {
minIndex := 0
maxIndex := bound - 1
for minIndex <= maxIndex {
midIndex := int((maxIndex + minIndex) / 2)
midItem := array[midIndex]
if number == midItem {
return midIndex
}
if midItem < number {
minIndex = midIndex + 1
} else if midItem > number {
maxIndex = midIndex - 1
}
}
return -1
}
func SortArray(array []int) {
for itemIndex, itemValue := range array {
for itemIndex != 0 && array[itemIndex-1] > itemValue {
array[itemIndex] = array[itemIndex-1]
itemIndex -= 1
}
array[itemIndex] = itemValue
}
}
func TestExponentialSearch(t *testing.T) {
random := rand.New(rand.NewSource(time.Now().UnixNano()))
array := make([]int, random.Intn(100-10)+10)
for i := range array {
array[i] = random.Intn(100)
}
SortArray(array)
for _, value := range array {
result := ExponentialSearch(array, value)
if result == -1 {
t.Fail()
}
}
}
