Tuesday, February 12, 2019

Exponential Search Program in Java

In this post we’ll see how to write Exponential search program in Java. Exponential search is a variation of Binary search, meaning it is also a divide and conquer algorithm how it differs is that rather than dividing the input array into two equal parts in Exponential search a range with in the input array is determined with in which the searched element would reside. Then using Binary search element is searched with in that range.

Exponential search is used to search elements in unbounded arrays.

How does Exponential search work

One of the prerequisite for the Exponential search is that the input array should be sorted.

Exponential search works in two stages. In the first stage a range is calculated that contains the searched element. In the second stage Binary search is done with in that range to search the element.

Exponential search starts by finding the first element that satisfies both of these conditions-

  1. Greater than the searched element
  2. Has index as a power of 2.

This index becomes the upper bound for the range, if such index is j then 2j-1 (or j/2) is the lower bound for the search.

Exponential search Java Program

public class ExponentialSearch {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] arr = {5, 65, 89, 3, 1, 10, 11, 22, 34, 43};
    Arrays.sort(arr);
    System.out.println("Sorted array- " + Arrays.toString(arr));
    System.out.println("Enter value to search: ");
    int searchElement = sc.nextInt();
    int index = exponentialSearch(arr, searchElement);
    if(index != -1){
      System.out.println("Searched item " + arr[index] + " found at index "+index);
    }else{
      System.out.println("Searched item " + searchElement + " not found in the array");
    }
    sc.close();
  }
    
  private static int exponentialSearch(int[] arr, int searchElement){
    int bound = 1;
    // increase upper bound 
    while (bound < arr.length && arr[bound] < searchElement) {
      bound *= 2;
    }
    // do binary search with in the range
    return binarySearch(arr, bound/2, Integer.min(bound + 1, arr.length), searchElement);
  }

  private static int binarySearch(int[] arr, int start, int end, int searchElement){
    // exit condition
    if(start > end){
      return -1;
    }        
    int middle = (start+end)/2;
    // element found
    if(searchElement == arr[middle]){
      return middle;
    }
    // left half
    if(searchElement < arr[middle]){
      return binarySearch(arr, start, middle-1, searchElement);
    }else{
      // right half
      return binarySearch(arr, middle+1, end, searchElement);        
    }
  }
}

Output

sorted array- [1, 3, 5, 10, 11, 22, 34, 43, 65, 89]
Enter value to search: 
10
Searched item 10 found at index 3

Exponential search Performance

The first stage of the algorithm where the range is determined takes O(log i) time, where i is the index of the searched element in the input array.

Second stage where Binary search is done also takes O(log i) for the given range. So the total time taken is 2*O(log i). Thus the time complexity of Exponential search is O(log i).

Space complexity of Exponential search is O(1), for recursive implementation of Binary search method calls are stacked for each recursive call making the space complexity as O(log i) in that case.

That's all for this topic Exponential Search Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Interpolation Search Program in Java
  2. Linear Search (Sequential Search) Java Program
  3. Merge Sort Program in Java
  4. Find Maximum And Minimum Numbers in a Given Matrix - Java Program
  5. Printing Numbers in Sequence Using Threads - Java Program

You may also like-

  1. Reading File in Java Using Scanner
  2. Creating PDF in Java Using iText
  3. Converting double to String in Java
  4. How to Convert Date And Time Between Different Time-Zones in Java
  5. this Keyword in Java With Examples
  6. How HashMap Internally Works in Java
  7. Semaphore in Java Concurrency
  8. Spring MVC File Download Example