fork download
copy 
  1. /**
  2.   * @brief Search for Magic Index hence an array index where 
  3.   * a[i]==i 
  4.   */
  5.  
  6. #include <iostream>
  7. #include <array>
  8. #include <assert.h>
  9. using namespace std; 
  10.  
  11. array<int, 11> data = {-40, -20, -1, 1,2,3,5,7,9,12,15}; 
  12.  
  13. template <typename T>
  14. class MaybeResult
  15. {
  16.   public: 
  17.   MaybeResult(const T& _val) : is_valid(true), val(_val) {}
  18.   MaybeResult() : is_valid(false), val() {}
  19.  
  20.   const bool is_valid; 
  21.   const T val; 
  22. }; 
  23.  
  24.  
  25.  
  26. template <typename T>
  27. MaybeResult<unsigned int> find_magic_index(const T& arr, const unsigned int l, const unsigned int r)
  28. {
  29.   if(r<l) return MaybeResult<unsigned int>(); 
  30.   if(l==r) return  (arr[r]==r)?MaybeResult<unsigned int>(r):MaybeResult<unsigned int>(); 
  31.   const unsigned int p = (l+r)/2; 
  32.   if(arr[p]==p) return MaybeResult<unsigned int>(p); 
  33.   if(arr[p] > p) return find_magic_index(arr, l, p); 
  34.   if(arr[p] < p) return (p>l)?find_magic_index(arr, p, r):find_magic_index(arr, r, r); 
  35.   return MaybeResult<unsigned int>(); 
  36. }
  37.  
  38.  
  39. int main() {
  40.   std::cout << "Hello World!\n";
  41.   assert(find_magic_index(array<int, 11>{-40, -20, -1, 1,2,3,5,7,9,12,15}, 0, data.size()-1).val == 7 ); 
  42.  
  43.   assert(find_magic_index(array<int, 11>{-40, -20, -1, 1,2,3,5,6,9,12,15}, 0, data.size()-1).is_valid == false ); 
  44.  
  45.   auto res = find_magic_index(array<int, 11>{-40, -20, -1, 1,2,3,5,7,9,12,15}, 0, data.size()-1); 
  46.   cout << (res.is_valid?to_string(res.val):"Not Found") << endl; 
  47. }
  48.  
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Hello World!
7
https://ideone.com/ez26KD
Search for Magic Index a[i]==i with Binary Search
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!