Back to Course

Algorithm

0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
    Stacks
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
Lesson 7, Topic 4
In Progress

Exponential Search

Lesson Progress
0% Complete

Exponential search is also known as doubling or galloping search. This mechanism is used to find the range where the search key may present. If L and U are the upper and lower bound of the list, then L and U both are the power of 2. For the last section, the U is the last position of the list. For that reason, it is known as exponential.

After finding the specific range, it uses the binary search technique to find the exact location of the search key.

KodNest Screenshot 23 1
An array with values and its index values (x=70)
KodNest Screenshot 24
We will use one while loop with following condition (i<n && arr[i]<=x) and if the condition is true, following statement will be executed i=i*2. i will be 1 first and then it will increase as per the coding, n is the length of the array.
KodNest Screenshot 25
when i will be 2, the condition will be true and i will become 4 because of i=i*2
KodNest Screenshot 26
When i will be 4, condition will become true and i will become 8
KodNest Screenshot 27
exponentialSearch method is stating the while method with necessary statement and now we will use binarySearch method to do the rest of the searching
KodNest Screenshot 28 1
Binary search on the arr, and finding the mid value of that which is 46 and we will get the second row from 46 to 99 value.
KodNest Screenshot 29
finding the mid value in the 2nd row and we will get the 70 to 99 value
KodNest Screenshot 30
KodNest Screenshot 31
finding the mid value and comparing the x value
KodNest Screenshot 32
Found the element
KodNest Screenshot 33
Printing the element found and calling of methods

The complexity of Exponential Search Technique

  1. Time Complexity: O(1) for the best case. O(log2 i) for average or worst case. Where i is the location where search key is present.
  2. Space Complexity: O(1)

Input and Output

Input:
A sorted list of data:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
The search key 780
Output:
Item found at location: 16

Algorithm

binarySearch(array, start, end, key)

Input: An sorted array, start and end location, and the search key

Output: location of the key (if found), otherwise wrong location.

Begin
   if start <= end then
      mid := start + (end - start) /2
      if array[mid] = key then
         return mid location
      if array[mid] > key then
         call binarySearch(array, mid+1, end, key)
      else when array[mid] < key then
         call binarySearch(array, start, mid-1, key)
   else
      return invalid location
End

exponentialSearch(array, start, end, key)

Input: An sorted array, start and end location, and the search key

Output: location of the key (if found), otherwise wrong location.

Begin
   if (end – start) <= 0 then
      return invalid location
   i := 1
   while i < (end - start) do
      if array[i] < key then
         i := i * 2 //increase i as power of 2
      else
         terminate the loop
   done
   call binarySearch(array, i/2, i, key)
End

Exponential Search Program in C

#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;
}

Output :

Element found at index 4
KodNest Training New Batch is starting on 02nd November 2020. Attend one week free demo classes.Register Now

New Report

Close