题目
假设一个单调递增的数组里的每个元素都是整数并且唯一。编写函数找出数组中任意一个数值等于其下标的元素。例如:在数组{-3,-1,1,3,5}中，数字3和它的下标相等。
解题思路
- 二分查找
- 和(2)题很相似，若中间数组的值刚好等于下标，则就找到
若中间数组的值大于下标，则下一轮找数组的左半边
若中间数组的值小于下标，则下一轮找数组的右半边
代码
class Solution{
public:
int getFirstk(int *sorted_array,int left,int right)
{
if(left <= right)
{
int index = (left + right) >> 1;
int mid = sorted_array[index];
if(sorted_array[index] == index)
{
return mid;
}
else if(sorted_array[index] > index)
{
right = index - 1;
}
else
{
left = index +1;
}
return getFirstk(sorted_array,left,right);
}
else
{
return -1;
}
}
};
