程序员面试金典： 9.9 递归和动态规划 9.3魔术索引

#include <iostream>
#include <stdio.h>

using namespace std;

/*
问题：在数组A[0 ... n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个
      有序整数数组，元素值各不相同，编写一个方法，在数组A中找出一个魔术索引，如果存在的话。
分析: 因为A{i] = i,所以魔术索引对应 A[i] - i = 0，
      可以猜想，将令数组A中A[i] = A[i] - i 得到的应该是类似如下这种
   ...-2 -1 0 0 0 1 2....
   问题转换成了为：二分查找，而且是二分查找中查找lowwer和upper的算法
二分查找之lowwer_bound:这个是找到大于等于某元素首次出现的位置
          upper_bound:找到大于元素第一次出现的位置

求下边界算法：设low,high表示数组A下标和上标
中间值<查找值，说明查找值在中间值的右侧，令下标low=middle+1，在[middle+1,high]中继续查找
中间值>查找值，中间值可能是解，找值在中间值及其左侧，令上标high = middle;
中间值=查找值，由于是要找到大于或等于某元素首次出现位置，那么当前值是有有可能的查找值应该在下标到当前中间值中继续查找，high=middle;

合并之后:
中间值<查找值，low = middle+1
中间值>=查找值，high=middle
何时终止？ 主要是判断low<high，继续；low > high，终止；low = high时，如果A[low] = 待查找值，直接返回
           low,否则返回-1

求上边界算法:
中间值<查找值，说明查找值在中间值右侧，令下标low=middle+1，在[middle+1,high]中继续查找
中间值>查找值，中间值可能是解，查找值在中间值及其左侧，令上标high = middle ;
中间值=查找值，中间值不可能是解，那么查找值应该在下标到当前中间值中继续查找，low=middle+1;

合并:
中间值<=查找值，low=middle+1
中间值>查找值，high = middle;

输入:
7(元素个数)
-3 -1 2 3 4 7 8
7
1 2 3 4 5 6 7
输出:
3
-1

关键:
1 二分查找之lowwer_bound:这个是找到大于等于某元素首次出现的位置
          upper_bound:找到大于元素第一次出现的位置

求下边界算法：设low,high表示数组A下标和上标
中间值<查找值，说明查找值在中间值的右侧，令下标low=middle+1，在[middle+1,high]中继续查找
中间值>查找值，中间值可能是解，找值在中间值及其左侧，令上标high = middle;
中间值=查找值，由于是要找到大于或等于某元素首次出现位置，那么当前值是有有可能的查找值应该在下标到当前中间值中继续查找，high=middle;

//二分查找值，寻找某个元素首次出现的下标
int lowwer_bound(int* pArray , int low , int high , int value)
{
 if(NULL == pArray || low > high || low < 0 || high < 0)
 {
  return -1;
 }
 int middle;
 while( low <= high ) // "="取的原因是，同一个区间需要去做最后一次判定，否则遗漏一次判定操作
 {
   middle = low + (high - low)/2;
   if(pArray[middle] < value )
   {
    low = middle + 1;
   }
   //但注意会陷入死循环，存在low=high,则A[low]=A[high] ,p[m] >= value的情况，这种说明已经找到了
   else
   {
    if( low == high )
    {
     //找到结果，直接返回
     if( pArray[low] >= value)
     {
      return low;
     }
     else
     {
      return -1;
     }
    }
    high = middle;
   }
 }
 //如果走到这里，就认为查找不到
 return -1;
}

2 求上边界算法:
中间值<查找值，说明查找值在中间值右侧，令下标low=middle+1，在[middle+1,high]中继续查找
中间值>查找值，中间值可能是解，查找值在中间值及其左侧，令上标high = middle ;
中间值=查找值，中间值不可能是解，那么查找值应该在下标到当前中间值中继续查找，low=middle+1;
*/

int upper_bound(int* pArray , int low , int high , int value)
{
 if(NULL == pArray || low > high || low < 0 || high < 0)
 {
  return -1;
 }
 int middle;
 while( low <= high )
 {
  middle = low + (high - low)/2;
  if(pArray[middle] <= value)
  {
   low = middle + 1;
  }
  else
  {
   if(low == high)
   {
     //找到结果，直接返回
     if( pArray[low] > value)
     {
      return low;
     }
     else
     {
      return -1;
     }
   }
   high = middle;
  }
 }
 return -1;
}

//二分查找值，寻找某个元素首次出现的下标
int lowwer_bound(int* pArray , int low , int high , int value)
{
 if(NULL == pArray || low > high || low < 0 || high < 0)
 {
  return -1;
 }
 int middle;
 while( low <= high ) // "="取的原因是，同一个区间需要去做最后一次判定，否则遗漏一次判定操作
 {
   middle = low + (high - low)/2;
   if(pArray[middle] < value )
   {
    low = middle + 1;
   }
   //但注意会陷入死循环，存在low=high,则A[low]=A[high] ,p[m] >= value的情况，这种说明已经找到了
   else
   {
    if( low == high )
    {
     //找到结果，直接返回
     if( pArray[low] >= value)
     {
      return low;
     }
     else
     {
      return -1;
     }
    }
    high = middle;
   }
 }
 //如果走到这里，就认为查找不到
 return -1;
}

//二分查找
int binarySearch(int* pArray , int low , int high , int value)
{
 if(NULL == pArray || low > high || low < 0 || high < 0)
 {
  return -1;
 }
 int middle;
 while( low <= high ) // "="取的原因是，同一个区间需要去做最后一次判定，否则遗漏一次判定操作
 {
   middle = low + (high - low)/2;
   if( pArray[middle] < value )
   {
    low = middle + 1;
   }
   else if( pArray[middle] > value )
   {
    high = middle - 1;
   }
   else
   {
    return middle;
   }
 }
 //如果发生low > high，肯定是找不到，返回-1
 return -1;
}

void process()
{
 int n;
 int num;
 while(cin >> n)
 {
  int* pArray = new int[n];
  for(int i = 0 ; i < n ; i++)
  {
   cin >> num;
   *(pArray + i) = num - i;
  }
  /*
  int low = lowwer_bound(pArray , 0 , n - 1 , value);
  int high = upper_bound(pArray , 0 , n - 1 , value);
  int result = binarySearch(pArray , 0 , n - 1 , value);
  cout << low << " " << high << " " << result << endl;
  */
  int result = binarySearch(pArray , 0 , n - 1 , 0);
  cout << result << endl;
  delete[] pArray;
 }
}

int main(int argc, char* argv[])
{
 process();
 getchar();
 return 0;
}