fork download
copy 
  1. #include <stdio.h>
  2.  
  3. // Utility function to find minimum of two numbers
  4. int min(int x, int y) {
  5.     return (x < y) ? x : y;
  6. }
  7.  
  8. // Binary search algorithm to return the position of
  9. // target x in the sub-array arr[low..high]
  10. int BinarySearch(int arr[], int low, int high, int x)
  11. {
  12.     // Base condition (search space is exhausted)
  13.     if (low > high)
  14.         return -1;
  15.  
  16.     // we find the mid value in the search space and
  17.     // compares it with target value
  18.  
  19.     int mid = (low + high)/2;    // overflow can happen
  20.     // int mid = low + (high - low)/2;
  21.  
  22.     // Base condition (target value is found)
  23.     if (x == arr[mid])
  24.         return mid;
  25.  
  26.     // discard all elements in the right search space
  27.     // including the mid element
  28.     else if (x < arr[mid])
  29.         return BinarySearch(arr, low,  mid - 1, x);
  30.  
  31.     // discard all elements in the left search space
  32.     // including the mid element
  33.     else
  34.         return BinarySearch(arr, mid + 1,  high, x);
  35. }
  36.  
  37. // Returns the position of target x in the given array of length n
  38. int ExponentialSearch(int arr[], int n, int x)
  39. {
  40.     int bound = 1;
  41.  
  42.     // find the range in which the target x would reside
  43.     while (bound < n && arr[bound] < x)
  44.         bound *= 2;    // calculate the next power of 2
  45.  
  46.     // call binary search on arr[bound/2 .. min(bound, n)]
  47.     return BinarySearch(arr, bound/2, min(bound, n), x);
  48. }
  49.  
  50. // Exponential search algorithm
  51. int main(void)
  52. {
  53.     int arr[] = {2, 5, 6, 8, 9, 10};
  54.     int target = 9;
  55.  
  56.     int n = sizeof(arr)/sizeof(arr[0]);
  57.     int index = ExponentialSearch(arr, n, target);
  58.  
  59.     if (index != -1)
  60.         printf("Element found at index %d", index);
  61.     else
  62.         printf("Element not found in the array");
  63.  
  64.     return 0;
  65. }
Success #stdin #stdout 0s 10320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Element found at index 4
https://ideone.com/1iWiFn
Exponential search algorithm
language:
C (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!