CC-8 : Implement Exponential Search Algorithm.

Description:

The Exponential search algorithm works on sorted lists. The algorithm partitions the list by using exponentially sized partitions (that is, the partition size doubles at each step). Given an input array and an element to be searched, search the required element in the input array using Exponential search.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 3, 22, 44, 67, 77, 96, 122, 144, 201,	122 found at index 6 76 found at index -1 3 found at index 0 201 found at index 8

Pseudocode:

Exponential Search(nums[], toSearch):

Integer array named nums, and integer named toSearch to be searched are received as input parameters.

Set integer variable currIdx to 1, we will use this variable to store the first index of partition in which are searching for required integer.

While (currIdx < nums.length) and nums[firstIdx] <= toSearch do the following steps:

Set currIdx=currIdx*2.

Set integer variable lastIdx to currIdx, we will use this variable to store the last index of partition in which are searching for required integer.

If (lastIdx > nums.length):

Set lastIdx=nums.length.

Return the index received from recursive calls to binarySearch(nums, currIdx/2,lastIdx, toSearch).

binarySearch(nums[], firstIdx, LastIdx, toSearch):

Integer array named nums and integer named toSearch to be searched are received as input parameters.

Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.

Set integer variable lastIdx to nums.length-1, we will use this variable to check the last index of partition in which are searching for required integer.

While (firstIdx <= lastIdx) do the following steps:

Set integer variable midCount to (lastIdx-firstIdx)/2.

Set integer variable midIdx to (firstIdx+midCount)to get mid index of current partition. We will use midIdx to partition the array into 2 parts.

If (nums[midIdx]==toSearch) return midIdx; this means have found the required element.

Else if nums[midIdx > toSearch then:

Set lastIdx=(midIdx-1) as we need to search in lower partition now.

Else:

Set firstIdx=midIdx+1, as we need to search in the higher partition now.

If toSearch is not found in code above return -1, as the required element does not exist within the input array.

Code:

public int exponentialSearch(int[] nums, int toSearch){
	if (nums[0] == toSearch) {return 0;}
	int currIdx=1;
	while ((currIdx< nums.length)&&(nums[currIdx]<=toSearch)) {
		currIdx=currIdx*2;
	}
	int lastIdx=currIdx;
	if (lastIdx > nums.length) {
		lastIdx=nums.length;
	}
	return binarySearch(nums, currIdx/2, lastIdx, toSearch);
}

public int binarySearch(int[] nums, int firstIdx, int lastIdx,int toSearch){
	while (firstIdx <= lastIdx) {
		int midCount=(lastIdx-firstIdx)/2;
		int midIdx=firstIdx+midCount;
		if (nums[midIdx]==toSearch) {
			return midIdx;
		} else { if (nums[midIdx]> toSearch) {
			lastIdx=midIdx-1;
		}else {
			firstIdx=midIdx+1;
		}
		}		
	}	
	return -1;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SearchExponentialSearch {

public int exponentialSearch(int[] nums, int toSearch){
	if (nums[0] == toSearch) {return 0;}
	int currIdx=1;
	while ((currIdx< nums.length)&&(nums[currIdx]<=toSearch)) {
		currIdx=currIdx*2;
	}
	int lastIdx=currIdx;
	if (lastIdx > nums.length) {
		lastIdx=nums.length;
	}
	return binarySearch(nums, currIdx/2, lastIdx, toSearch);
}

public int binarySearch(int[] nums, int firstIdx, int lastIdx,int toSearch){
	while (firstIdx <= lastIdx) {
		int midCount=(lastIdx-firstIdx)/2;
		int midIdx=firstIdx+midCount;
		if (nums[midIdx]==toSearch) {
			return midIdx;
		} else { if (nums[midIdx]> toSearch) {
			lastIdx=midIdx-1;
		}else {
			firstIdx=midIdx+1;
		}
		}		
	}	
	return -1;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	SearchExponentialSearch search=new SearchExponentialSearch();
	int[] nums= { 3,22,44,67,77,96,122, 144, 201};
	int toSearch=122;
	retVal=search.exponentialSearch(nums, toSearch);
	
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	
	System.out.println("\n\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=76;
	retVal=search.exponentialSearch(nums, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=3;
	retVal=search.exponentialSearch(nums, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=201;
	retVal=search.exponentialSearch(nums, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}



}