Exponential Search
Last Updated :
28 Mar, 2023
The name of this searching algorithm may be misleading as it works in O(Log n) time. The name comes from the way it searches an element.
Given a sorted array, and an element x to be
searched, find position of x in the array.
Input: arr[] = {10, 20, 40, 45, 55}
x = 45
Output: Element found at index 3
Input: arr[] = {10, 15, 25, 45, 55}
x = 15
Output: Element found at index 1
We have discussed, linear search, binary search for this problem.
Exponential search involves two steps:
- Find range where element is present
- Do Binary Search in above found range.
How to find the range where element may be present?
The idea is to start with subarray size 1, compare its last element with x, then try size 2, then 4 and so on until last element of a subarray is not greater.
Once we find an index i (after repeated doubling of i), we know that the element must be present between i/2 and i (Why i/2? because we could not find a greater value in previous iteration)
Given below are the implementations of above steps.
C++
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int, int, int);
int exponentialSearch(int arr[], int n, int x)
{
if (arr[0] == x)
return 0;
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
return binarySearch(arr, i/2,
min(i, n-1), x);
}
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = exponentialSearch(arr, n, x);
(result == -1)? cout <<"Element is not present in array"
: cout <<"Element is present at index " << result;
return 0;
}
|
C
#include <stdio.h>
#include <time.h>
#include <math.h>
#define min
int binarySearch(int arr[], int, int, int);
int exponentialSearch(int arr[], int n, int x)
{
if (arr[0] == x)
return 0;
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
return binarySearch(arr, i/2,
min(i, n-1), x);
}
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = exponentialSearch(arr, n, x);
(result == -1)? printf("Element is not
present in array")
: printf("Element is present
at index %d",
result);
return 0;
}
|
Java
import java.util.Arrays;
class GFG
{
static int exponentialSearch(int arr[],
int n, int x)
{
if (arr[0] == x)
return 0;
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
return Arrays.binarySearch(arr, i/2,
Math.min(i, n-1), x);
}
public static void main(String args[])
{
int arr[] = {2, 3, 4, 10, 40};
int x = 10;
int result = exponentialSearch(arr,
arr.length, x);
System.out.println((result < 0) ?
"Element is not present in array" :
"Element is present at index " +
result);
}
}
|
Python3
def binarySearch( arr, l, r, x):
if r >= l:
mid = l + ( r-l ) // 2
if arr[mid] == x:
return mid
if arr[mid] > x:
return binarySearch(arr, l,
mid - 1, x)
return binarySearch(arr, mid + 1, r, x)
return -1
def exponentialSearch(arr, n, x):
if arr[0] == x:
return 0
i = 1
while i < n and arr[i] <= x:
i = i * 2
return binarySearch( arr, i // 2,
min(i, n-1), x)
arr = [2, 3, 4, 10, 40]
n = len(arr)
x = 10
result = exponentialSearch(arr, n, x)
if result == -1:
print ("Element not found in the array")
else:
print ("Element is present at index %d" %(result))
|
C#
using System;
class GFG {
static int exponentialSearch(int []arr,
int n, int x)
{
if (arr[0] == x)
return 0;
int i = 1;
while (i < n && arr[i] <= x)
i = i * 2;
return binarySearch(arr, i/2,
Math.Min(i, n - 1), x);
}
static int binarySearch(int []arr, int l,
int r, int x)
{
if (r >= l)
{
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
public static void Main()
{
int []arr = {2, 3, 4, 10, 40};
int n = arr.Length;
int x = 10;
int result = exponentialSearch(arr, n, x);
if (result == -1)
Console.Write("Element is not
present in array");
else
Console.Write("Element is
present at index "
+ result);
}
}
|
PHP
<?php
function exponentialSearch($arr, $n, $x)
{
if ($arr[0] == $x)
return 0;
$i = 1;
while ($i< $n and $arr[$i] <=$x)
$i = $i * 2;
return binarySearch($arr, $i / 2,
min($i, $n - 1), $x);
}
function binarySearch($arr, $l,
$r, $x)
{
if ($r >= $l)
{
$mid = $l + ($r - $l)/2;
if ($arr[$mid] == $x)
return $mid;
if ($arr[$mid] > $x)
return binarySearch($arr, $l,
$mid - 1, $x);
return binarySearch($arr, $mid + 1,
$r, $x);
}
return -1;
}
$arr = array(2, 3, 4, 10, 40);
$n = count($arr);
$x = 10;
$result = exponentialSearch($arr, $n, $x);
if($result == -1)
echo "Element is not present in array";
else
echo "Element is present at index ",
$result;
?>
|
Javascript
<script>
function binarySearch(arr, l, r, x)
{
if (r >= l)
{
let mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
function exponentialSearch(arr, n, x)
{
if (arr[0] == x)
return 0;
let i = 1;
while (i < n && arr[i] <= x)
i = i * 2;
return binarySearch(arr, i/2,
Math.min(i, n - 1), x);
}
let arr = [2, 3, 4, 10, 40];
let n = arr.length;
let x = 10;
let result = exponentialSearch(arr, n, x);
if (result == -1)
document.write("Element is not present in array");
else
document.write("Element is present at index " + result);
</script>
|
Output
Element is present at index 3
Time Complexity : O(Log n)
Auxiliary Space : The above implementation of Binary Search is recursive and requires O(Log n) space. With iterative Binary Search, we need only O(1) space.
Applications of Exponential Search:
- Exponential Binary Search is particularly useful for unbounded searches, where size of array is infinite. Please refer Unbounded Binary Search for an example.
- It works better than Binary Search for bounded arrays, and also when the element to be searched is closer to the first element.
Reference:
https://en.wikipedia.org/wiki/Exponential_search
Approach 2: Iterative implementation
Here’s how it works:
We start with an index i equal to 1 and repeatedly double it until either i is greater than or equal to the length of the array or the value at index i is greater than or equal to the target value x.
We then perform a binary search on the range [i/2, min(i, n-1)], where n is the length of the array. This range is guaranteed to contain the target value, if it is present in the array, because we know that the target value must be greater than or equal to the value at index i/2 and less than or equal to the value at index min(i, n-1).
If we find the target value in the binary search, we return its index. Otherwise, we return -1 to indicate that the target value is not present in the array.
C++
#include<bits/stdc++.h>
using namespace std;
int exponential_search(vector<int> arr,int x){
int n = arr.size();
if(n == 0)
return -1;
int i = 1;
while(i < n and arr[i] < x)
i *= 2;
int left = i /2;
int right = min(i, n-1);
while(left <= right){
int mid = (left + right)/2;
if(arr[mid] == x) return mid;
else if(arr[mid] < x) left = mid + 1;
else right = mid - 1;
}
return -1;
}
int main(){
vector<int> arr = {2, 3, 4, 10, 40};
int n = arr.size();
int x = 10;
int result = exponential_search(arr, x);
if(result == -1){
cout << "Element not found in the array";
}
else{
cout << "Element is present at index " << result << endl;
}
return 0;
}
|
Java
import java.util.*;
class Main {
public static int exponential_search(ArrayList<Integer> arr, int x) {
int n = arr.size();
if (n == 0)
return -1;
int i = 1;
while (i < n && arr.get(i) < x)
i *= 2;
int left = i / 2;
int right = Math.min(i, n - 1);
while (left <= right) {
int mid = (left + right) / 2;
if (arr.get(mid) == x)
return mid;
else if (arr.get(mid) < x)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(2, 3, 4, 10, 40));
int n = arr.size();
int x = 10;
int result = exponential_search(arr, x);
if (result == -1) {
System.out.println("Element not found in the array");
}
else {
System.out.println("Element is present at index " + result);
}
}
}
|
Python
def exponential_search(arr, x):
n = len(arr)
if n == 0:
return -1
i = 1
while i < n and arr[i] < x:
i *= 2
left = i // 2
right = min(i, n-1)
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
arr = [2, 3, 4, 10, 40]
n = len(arr)
x = 10
result = exponential_search(arr, x)
if result == -1:
print ("Element not found in the array")
else:
print ("Element is present at index %d" %(result))
|
C#
using System;
using System.Collections.Generic;
class Program
{
static int exponential_search(List<int> arr, int x)
{
int n = arr.Count;
if (n == 0)
return -1;
int i = 1;
while (i < n && arr[i] < x)
i *= 2;
int left = i / 2;
int right = Math.Min(i, n - 1);
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] == x) return mid;
else if (arr[mid] < x) left = mid + 1;
else right = mid - 1;
}
return -1;
}
static void Main(string[] args)
{
List<int> arr = new List<int> { 2, 3, 4, 10, 40 };
int n = arr.Count;
int x = 10;
int result = exponential_search(arr, x);
if (result == -1)
{
Console.WriteLine("Element not found in the array");
}
else
{
Console.WriteLine("Element is present at index " + result);
}
}
}
|
Javascript
function exponential_search(arr, x) {
const n = arr.length;
if (n == 0) {
return -1;
}
let i = 1;
while (i < n && arr[i] < x) {
i *= 2;
}
const left = Math.floor(i / 2);
const right = Math.min(i, n - 1);
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] == x) {
return mid;
} else if (arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
const arr = [2, 3, 4, 10, 40];
const n = arr.length;
const x = 10;
const result = exponential_search(arr, x);
if (result == -1) {
console.log("Element not found in the array");
} else {
console.log(`Element is present at index ${result}`);
}
|
Output
Element is present at index 3
Time Complexity : O(Log n)
Auxiliary Space : O(1) space.
Please Login to comment...