FOR FREE MATERIALS

Exponential search is a searching technique where a range is first found in between which the searched value exists. Then on that particular range, the binary search technique is applied. For exponential search, the list should be in sorted order. First, the subarray size is taken as 1 then the last element of that particular range is compared with the searched value, then the subarray size is taken as 2, then 4, and so on. When the last element of the sub-array is greater than the searched element then the process is stopped. Now, we can say that the searched element is present between i/2 and i (if the last index of the subarray greater than the searched element is i). The range is i/2 and i because in the previous iteration the last element was not greater than the searched element.  

EXAMPLE:

Suppose the list is:

Let the searched element be 47.

First the range is set to 1. Now the value of index 1 (i.e. 20) will be compared with the searched element (47). 

As the searched element is not lesser than the value of index 1 then the next range will be set to 2 * 1 = 2. Now again the value of index 2 (i.e. 35) will be compared with the searched element (47).

As 35 is lesser than 47 then the bound will be set to 2 * 2 = 4. The searched element 47 will now be compared with the value at index 4 i.e. 59.

Now the element is not less than 47. So, the increment of the bound will be stopped. Now, the binary search will be performed between indexes 2 and 4.

The lower index is 2 and the upper index is 4.

So, the middle index will be calculated as:

mid = (lower index + upper index)/2

        = (2 + 4)/2

        = 6/2

        = 3

Now the searched value (47) will be compared with the value of index 3(47).

As their values are matched then the position of the element will be printed.

INPUT: Array elements
OUTPUT: the position of the element if found
PROCESS:
Step 1: [taking the input]
	Read n [number of elements]
	For i=0 to n-1 repeat
		Read a[i]
	[end of ‘for’ loop]
	Read x [the element which is to be searched]
Step 2: [searching the element]
	Set bound<-1
	While bound<n and a[bound]<x repeat
		Set bound<-bound*2
	[End of ‘while’ loop]
Set indx<-binary_search(a,bound/2,minimum of (bound,n),x)
[‘binary_search’ is a function defined in step 3]
	If indx≠-1 then
		Print "Element x found at index indx"
	else
		print "Element not found"
	[End of ‘if’]
Step 3: [function ‘binary_search(a[],l,h,x)’]
	if l>h then
		return -1
	[end of ‘if’]
	Set mid<-(l+h)/2
	if  x=a[mid] then
		return mid
	else if x<a[mid] then
		return binary_search(a,l,mid-1,x)
	else
		return binary_search(a,mid+1,h,x)
	[End of ‘if’]
[End of function ‘binary_search()’]
Step 4: Stop.