fork download
copy 
  1. #include <bits/stdc++.h>
  2. //#define FIN "cautbin.in"
  3. //#define FOUT "cautbin.out"
  4.  
  5. using namespace std;
  6.  
  7. //returns the largest index such that arr[i] == key
  8. // or -1 whether the key is not in the array
  9. int binary_search0(int *arr, int lo, int hi, int key) {
  10.  
  11.     if(lo > hi) {
  12.       return -1;
  13.     }
  14.  
  15.     int middle = (lo+hi)>>1;
  16.  
  17.     if(arr[middle] == key) {
  18.  
  19.           if(middle < hi) {
  20.  
  21.                if(arr[middle+1] == key) {
  22.  
  23.                   return binary_search0(arr, middle+1, hi, key);
  24.  
  25.                } else {
  26.  
  27.                  return middle;
  28.                }
  29.           } else {
  30.  
  31.             return middle;
  32.           }
  33.     } else if(arr[middle] < key) {
  34.  
  35.           return binary_search0(arr, middle+1, hi, key);
  36.  
  37.     } else {
  38.  
  39.           return binary_search0(arr, lo, middle-1, key);
  40.     }
  41. }
  42.  
  43. //returns the largest index such as arr[i]<=key; such an index it will always exist.
  44. int binary_search1(int *arr, int lo, int hi, int key) {
  45.  
  46.  
  47.       if(lo > hi) {
  48.  
  49.         return -1;
  50.       }
  51.  
  52.       int middle = (lo + hi) / 2;
  53.  
  54.       if(arr[middle] <= key) {
  55.  
  56.                if(middle < hi) {
  57.  
  58.                      if(arr[middle+1] > key) {
  59.  
  60.                        return middle;
  61.  
  62.                      } else {
  63.  
  64.                        return binary_search1(arr, middle + 1, hi, key);
  65.                      }
  66.  
  67.                } else {
  68.  
  69.                  return middle;
  70.                }
  71.  
  72.       } else {
  73.  
  74.         return binary_search1(arr, lo, middle-1, key);
  75.       }
  76.  
  77. }
  78.  
  79. //returns the smallest index such as arr[i]>=key; such an index it will always exist.
  80. int binary_search2(int *arr, int lo, int hi, int key) {
  81.  
  82.     if(lo > hi) {
  83.  
  84.       return -1;
  85.     }
  86.  
  87.     int middle = (lo + hi) / 2;
  88.  
  89.     if(arr[middle] >= key) {
  90.  
  91.              if(lo < middle) {
  92.  
  93.                    if(arr[middle-1] < key) {
  94.  
  95.                      return middle;
  96.  
  97.                    } else {
  98.  
  99.                      return binary_search2(arr, lo, middle-1, key);
  100.                    }
  101.  
  102.              } else {
  103.  
  104.                return middle;
  105.              }
  106.  
  107.     } else {
  108.  
  109.       return binary_search2(arr, middle+1, hi, key);
  110.     }
  111. }
  112.  
  113. int main(int argc, char const *argv[]) {
  114.  
  115.   //ifstream fin(FIN);
  116.   //ofstream fout(FOUT);
  117.  
  118.   typedef int (*fnPointer)(int*, int, int, int);
  119.  
  120.   int length;
  121.   cin>>length;
  122.   int array[length];
  123.  
  124.   for(int i = 0; i < length; ++i) cin>>array[i];
  125.  
  126.   fnPointer fn[ 3 ] = {binary_search0,binary_search1,binary_search2};
  127.  
  128.   int numOps;
  129.  
  130.   cin>>numOps;
  131.  
  132.   while(numOps--) {
  133.  
  134.     int op, value;
  135.  
  136.     cin>>op>>value;
  137.  
  138.     int index = fn[op](array, 0, length-1, value);
  139.  
  140.     if(index == -1) {
  141.  
  142.       cout<<index<<"\n";
  143.  
  144.     } else {
  145.  
  146.       cout<<index+1<<"\n";
  147.     }
  148.   }
  149.  
  150.    //fin.close();
  151.    //fout.close();
  152.  
  153.    return 0;
  154.  }
  155.  
Success #stdin #stdout 0.01s 5472KB
comments (?)
stdin
copy 
5
1 3 3 3 5
3
0 3
1 3
2 3
stdout
copy 
4
4
2
https://ideone.com/0WVBSi
Binary Search Problem Infoarena
language:
C++ (gcc 8.3)
created:
1 year 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!