剑指offer——58数组中数值和下标相等的元素

题目三：

　　数组中数值和下标相等的元素。
　　假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组{-3，-1，1，3，5}中，数字3和它的下标相等。

题解：

　　使用二分法，下角标小于其值，目标值在左边，下角标大于其值，目标值在右边。

 1 int findThatNum(const vector<int>&data)
 2 {
 3     if (data.size() == 0)return -1;
 4     int L = 0, R = data.size() - 1, M;
 5     while (L >= 0 && R < data.size() && L <= R)
 6     {
 7         M = (R - L) / 2 + L;
 8         if (data[M] == M)return M; 
 9         else if (data[M] > M)R = M - 1;//下角标小于其值，目标值在左边
10         else L = M + 1;//下角标大于其值，目标值在右边
11     }
12     return -1;
13 }