Exponential Search in Kotlin

by

Exponential search is a search algorithm that is used to find an element in a sorted array by repeatedly doubling the search range until the element is found or the search range exceeds the size of the array.

The algorithm works as follows:

  1. Start with a range that covers the entire array.
  2. Check the middle element of the range.
  3. If the middle element is equal to the target element, return its index.
  4. If the middle element is greater than the target element, search in the left half of the range.
  5. If the middle element is smaller than the target element, double the size of the range and continue the search in the new range.
  6. Repeat steps 2-5 until the element is found or the search range exceeds the size of the array.
Kotlin
fun exponentialSearch(arr: IntArray, target: Int): Int {
    if (arr.isEmpty()) return -1 // empty array

    // Find the range for binary search by doubling the index until it is greater than or equal to the target
    var i = 1
    while (i < arr.size && arr[i] <= target) {
        i *= 2
    }

    // Perform binary search within the found range
    var left = i / 2
    var right = minOf(i, arr.size - 1)
    while (left <= right) {
        val mid = (left + right) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }

    return -1 // target not found
}

how the exponentialSearch function works:

  1. Check if the input array is empty. If so, return -1 as the target element cannot be found in an empty array.
  2. Initialize a variable i to 1, which will be used to find the range for binary search.
  3. Use a while loop to keep doubling i until it is greater than or equal to the target element or until it reaches the end of the array. This is the exponential search step. The loop condition i < arr.size && arr[i] <= target checks that the current index is within the bounds of the array and that the value at that index is less than or equal to the target.
  4. Once the range for binary search has been determined, initialize variables left and right to the first and last indices of the range, respectively. The left index is set to i / 2 because i is currently greater than the target element, so the range for binary search should start from i / 2.
  5. Perform binary search within the range by using another while loop. The loop condition left <= right checks that there are still elements in the search range.
  6. Find the middle index of the search range by computing (left + right) / 2.
  7. Compare the value at the middle index with the target element. If they are equal, return the index of the middle element.
  8. If the middle element is less than the target, update the left index to mid + 1, since the target element must be in the right half of the search range.
  9. If the middle element is greater than the target, update the right index to mid - 1, since the target element must be in the left half of the search range.
  10. If the target element is not found in the search range, return -1.

Exponential search has a time complexity of O(log n), where n is the size of the array. It is particularly useful when the size of the array is unknown, as it avoids the need to determine the size before searching. However, it requires the array to be sorted, and is typically slower than binary search for small arrays.

Kotlin
fun main() {
    val arr = intArrayOf(20,30,40,50,60,70,80,90)
	val index = exponentialSearch(arr, 30)
    if (index != -1) {
    	println("Target found at index $index")
	} 
    else {
    	println("Target not found in the array")
	}
}
fun exponentialSearch(arr: IntArray, target: Int): Int {
    if (arr.isEmpty()) return -1 // empty array

    // Find the range for binary search by doubling the index until it is greater than or equal to the target
    var i = 1
    while (i < arr.size && arr[i] <= target) {
        i *= 2
    }

    // Perform binary search within the found range
    var left = i / 2
    var right = minOf(i, arr.size - 1)
    while (left <= right) {
        val mid = (left + right) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }

    return -1 // target not found
}

Leave a Comment