Exponential Search
We Know, linear search and binary search
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++ program to find an element x in a
sorted array using Exponential search. */
#include <bits/stdc++.h>
using namespace std;
/* A recursive binary search function. It returns location of x in given array arr[l..r] is present, otherwise -1 */
int binarySearch(int arr[], int l, int r, int x)
{
if (l <= r) {
int mid = l + (r - l) / 2;
/* Check if x is present at mid */
if(arr[mid] == x)
return mid;
/* If x greater, ignore left half */
if(arr[mid] < x)
return binarySearch(arr, l, mid-1, x);
/* If x is smaller, ignore right half */
return binarySearch(arr, mid+1, r, x);
}
/* if we reach here, then element was not present */
return -1;
}
/*Returns position of first occurrence of x in array */
int exponentialSearch(int arr[], int n, int x)
{
/* If x is present at first location itself */
if (arr[0] == x)
return 0;
/* Find range for binary search by repeated doubling */
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
/* Call binary search for the found range. */
return binarySearch(arr, i/2, min(i, n-1), x);
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
/* Find the index of 'x' using Exponential Search */
int result = exponentialSearch(arr, n, x);
/* Print the index where 'x' is located */
cout << " \nNumber " << x << " is at index " << result;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
/* A recursive binary search function. It returns location of x in given array arr[l..r] is present, otherwise -1 */
int binarySearch(int arr[], int l, int r, int x)
{
if (l <= r) {
int mid = l + (r - l) / 2;
/* Check if x is present at mid */
if(arr[mid] == x)
return mid;
/* If x greater, ignore left half */
if(arr[mid] < x)
return binarySearch(arr, l, mid-1, x);
/* If x is smaller, ignore right half */
return binarySearch(arr, mid+1, r, x);
}
/* if we reach here, then element was not present */
return -1;
}
/*Returns position of first occurrence of x in array */
int exponentialSearch(int arr[], int n, int x)
{
/* If x is present at first location itself */
if (arr[0] == x)
return 0;
/* Find range for binary search by repeated doubling */
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
/* Call binary search for the found range. */
return binarySearch(arr, i/2, min(i, n-1), x);
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
/* Find the index of 'x' using Exponential Search */
int result = exponentialSearch(arr, n, x);
/* Print the index where 'x' is located */
cout << " \nNumber " << x << " is at index " << result;
return 0;
}
Output :
Number 10 is 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.