Given a sorted array of integers and a target value, find out if a target exists in the array or not in O(log(n)) time. If target exists in the array, print index of it.
For example,
Input: A[] = [2, 3, 5, 7, 9]
target = 7
Output:Element found at index 3
Input: A[] = [1, 4, 5, 8, 9]
target = 2
Output:Element not found
Exponential search is an algorithm used for searching sorted, unbounded/infinite arrays. The idea is to determine a range that the target value resides in and perform a Binary Search within that range. Assuming that the array is sorted in ascending order, it looks for the first exponent k, where the value 2k is greater than the search key. Now 2k and 2k-1 becomes the upper bound and lower bound for the binary search algorithm respectively.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <stdio.h> // Utility function to find minimum of two numbers int min(int x, int y) { return (x < y) ? x : y; } // Binary search algorithm to return the position of // target x in the sub-array arr[low..high] int BinarySearch(int arr[], int low, int high, int x) { // Base condition (search space is exhausted) if (low > high) return -1; // we find the mid value in the search space and // compares it with target value int mid = (low + high)/2; // overflow can happen // int mid = low + (high - low)/2; // Base condition (target value is found) if (x == arr[mid]) return mid; // discard all elements in the right search space // including the mid element else if (x < arr[mid]) return BinarySearch(arr, low, mid - 1, x); // discard all elements in the left search space // including the mid element else return BinarySearch(arr, mid + 1, high, x); } // Returns the position of target x in the given array of length n int ExponentialSearch(int arr[], int n, int x) { int bound = 1; // find the range in which the target x would reside while (bound < n && arr[bound] < x) bound *= 2; // calculate the next power of 2 // call binary search on arr[bound/2 .. min(bound, n)] return BinarySearch(arr, bound/2, min(bound, n), x); } // Exponential search algorithm int main(void) { int arr[] = {2, 5, 6, 8, 9, 10}; int target = 9; int n = sizeof(arr)/sizeof(arr[0]); int index = ExponentialSearch(arr, n, target); if (index != -1) printf("Element found at index %d", index); else printf("Element not found in the array"); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
class ExponentialSearch { // Binary search algorithm to return the position of // key x in the sub-array A[left..right] private static int binarySearch(int[] A, int left, int right, int x) { // Base condition (search space is exhausted) if (left > right) { return -1; } // we find the mid value in the search space and // compares it with key value int mid = (left + right) / 2; // overflow can happen. Use // int mid = left + (right - left) / 2; // Base condition (key value is found) if (x == A[mid]) { return mid; } // discard all elements in the right search space // including the mid element else if (x < A[mid]) { return binarySearch(A, left, mid - 1, x); } // discard all elements in the left search space // including the mid element else { return binarySearch(A, mid + 1, right, x); } } // Returns the position of key x in the array A of length n public static int exponentialSearch(int[] A, int x) { int bound = 1; // find the range in which the key x would reside while (bound < A.length && A[bound] < x) { bound *= 2; // calculate the next power of 2 } // call binary search on A[bound/2 .. min(bound, n)] return binarySearch(A, bound/2, Integer.min(bound, A.length), x); } public static void main(String[] args) { int[] A = {2, 5, 6, 8, 9, 10}; int key = 9; int index = exponentialSearch(A, key); if (index != -1) System.out.println("Element found at index " + index); else System.out.println("Element not found in the array"); } } |
Output:
Element found at index 4
Performance:
Exponential search takes O(log(i)) time where i is the position of the target in the array, if the target is in the array, or the position where the target should be, if it is not in the array.
Exponential search can also be used to search in bounded arrays. It can even out-perform binary search, when the target is near the beginning of the array. This is because exponential search will run in O(log i) time, where i is the index of the element being searched for in the array, whereas binary search would run in O(log(n)) time, where n is the number of elements in the array.
Exercise: Find where a strictly increasing function (f(x) > f(x-1) for all values of x) becomes positive for the first time. Consider f(x) = x2 + 2x – 400. It becomes positive for first time for x = 20
References: https://en.wikipedia.org/wiki/Exponential_search
Thanks for reading.
Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
Thank you! It is always good to know about new, interesting algorithms..