Magic Index

CrackingTheCodeInterview-8.3.cpp

#include <iostream>

using namespace std;

int magicSearch(int arr[], int start, int end) {
  if (start > end)
    return -1;
  
  int index = (start + end) / 2;
  
  if (arr[index] == index)
    return index;
  
  int res = magicSearch(arr,start,min(arr[index],index-1));
  if (res != -1)
    return res;
  
  return magicSearch(arr,max(arr[index],index+1),end);
}

int magicSearch(int arr[], int size) {
  return magicSearch(arr, 0, size); 
}


int main() {
  int arr[] = {-10,-1,4,4,4,17};
  
  cout << magicSearch(arr,sizeof(arr)/sizeof(int)) << endl;
  return 0;
}