fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. void divide(int lo, int hi, int &m) {
  6.  
  7.     m = (lo + hi) >> 1;
  8. }
  9.  
  10. //solve recursively
  11. void searchbin(int vec[], int left, int right, int x, int &pos) {
  12.  
  13.     int middle;
  14.  
  15.     if(left <= right) {
  16.  
  17.         //truncate the interval
  18.         divide(left, right, middle);
  19.  
  20.         //compare the middle element
  21.         if( vec[ middle ] == x) { pos = middle; }
  22.  
  23.         else if(x < vec[middle]) searchbin(vec, left, middle - 1, x, pos);
  24.  
  25.                        else
  26.                                  searchbin(vec, middle + 1, right, x, pos);
  27.     }
  28.  
  29. }
  30.  
  31. //solve recursively
  32. int binsearch(int vec[], int lo, int hi, int x) {
  33.  
  34.     if(lo > hi) return -1;
  35.  
  36.     int m;
  37.  
  38.     m = (lo + hi) >> 1;
  39.  
  40.     if(vec[ m ] == x) return m + 1;
  41.  
  42.     else if(vec[ m ] > x) return binsearch(vec, lo, m - 1, x);
  43.  
  44.                   else
  45.  
  46.                           return binsearch(vec, m + 1, hi, x);
  47. }
  48.  
  49. //solve iteratively
  50. int _searchbin(int vec[], int left, int right, int x) {
  51.  
  52.      int pos = -1,
  53.          m;
  54.  
  55.      while(left <= right) {
  56.  
  57.             m = (left + right) >> 1;
  58.  
  59.            if(vec[ m ] == x) {
  60.  
  61.                    pos = m;
  62.                    break;
  63.            }
  64.  
  65.            else if(vec[m] > x) {
  66.  
  67.                    right = m - 1;
  68.  
  69.            } else {
  70.  
  71.                    left = m + 1;
  72.            }
  73.      }
  74.  
  75.      return pos + 1;
  76. }
  77.  
  78. int main(int argc, char const *argv[]) {
  79.  
  80.   int vec[] = {17,33,73,75,78,90,91,92,100},
  81.       n,
  82.       r,
  83.       search,
  84.       pos = -1;
  85.   n = sizeof(vec)/sizeof(vec[0]);
  86.  
  87.   cin>>search;
  88.  
  89.   searchbin(vec, 0, n - 1, search, pos);
  90.  
  91.   if(pos == -1) cout<<"Not Found!";
  92.  
  93.          else
  94.  
  95.                cout<<"Found [recursively] on position: " << pos+1;
  96.  
  97.   cout<<endl;
  98.   r = binsearch(vec, 0, n - 1, search);
  99.   cout<<"[recursive] Find at position: "<<r<<endl;
  100.  
  101.   r = _searchbin(vec, 0, n - 1, search);
  102.   if( r )   cout<<"[recursive] Find at position: "<<r<<endl;
  103.         else 
  104.            cout<<"[iterative] Not Found!";
  105.   return 0;
  106. }
Success #stdin #stdout 0s 5412KB
comments (?)
stdin
copy 
17
stdout
copy 
Found [recursively] on position: 1
[recursive] Find at position: 1
[recursive] Find at position: 1
https://ideone.com/nGkN4o
Binary Search - Iterative and Recursive.
language:
C++ (gcc 8.3)
created:
3 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!