Introduction

Exponential search is a search algorithm that is efficient for searching in a sorted array. It works by
finding a range where the target value may exist and then performing a binary search within that range.
This method is particularly useful for unbounded or infinite lists.

Program Structure

The program consists of the following main components:

• ExponentialSearch Function: This function finds the range for the binary search.
• BinarySearch Function: This function performs a binary search within the specified range.
• Main Function: This is the entry point of the program where we define the sorted array
  and the target value, and call the search functions.

Go Implementation

package main

import (
    "fmt"
)

// BinarySearch performs binary search in the array.
func BinarySearch(arr []int, left, right, target int) int {
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        }
        if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

// ExponentialSearch finds the target in a sorted array using exponential search.
func ExponentialSearch(arr []int, target int) int {
    if arr[0] == target {
        return 0
    }

    // Find range for binary search
    index := 1
    for index < len(arr) && arr[index] <= target {
        index *= 2
    }

    // Call binary search for the found range
    return BinarySearch(arr, index/2, min(index, len(arr)-1), target)
}

// min is a utility function to find the minimum of two integers.
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

// Main function to execute the program
func main() {
    arr := []int{2, 3, 4, 10, 40}
    target := 10

    result := ExponentialSearch(arr, target)

    if result == -1 {
        fmt.Println("Element not found in the array.")
    } else {
        fmt.Printf("Element found at index: %d\n", result)
    }
}

Documentation

Functions

• BinarySearch(arr []int, left int, right int, target int) int
  • Parameters:
    • arr: The sorted array in which to search.
    • left: The starting index of the search range.
    • right: The ending index of the search range.
    • target: The value to search for.
  • Returns: The index of the target if found, otherwise -1.
• ExponentialSearch(arr []int, target int) int
  • Parameters:
    • arr: The sorted array in which to search.
    • target: The value to search for.
  • Returns: The index of the target if found, otherwise -1.
• min(a int, b int) int
  • Parameters:
    • a: First integer.
    • b: Second integer.
  • Returns: The minimum of the two integers.

Conclusion

The exponential search algorithm is an efficient method for searching through sorted arrays.
By leveraging both exponential growth and binary search, it optimizes the search process, particularly
for large datasets. The provided Go implementation illustrates how to apply this algorithm effectively.