// 面试题53（三）：数组中数值和下标相等的元素
// 题目：假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实
// 现一个函数找出数组中任意一个数值等于其下标的元素。例如，在数组{-3, -1,
// 1, 3, 5}中，数字3和它的下标相等。 //思想：因为这里也是递增的，如果中间点的值大于下标，那后面所有值都会大于相应下标，同理中间点小于下标，前面都会小于下标
#include <iostream> int GetNumberSameAsIndex(const int* numbers, int length)
{
if (numbers == nullptr || length <= )
return -; int left = ;
int right = length - ;
while (left <= right)
{
int middle = left + ((right - left) >> );
if (numbers[middle] == middle)//第一种情况，中间点直接中了
return middle; if (numbers[middle] > middle)//第二种情况，中间点值大于坐标，向左区间找
right = middle - ;
else//第三种情况，中间点值小于坐标，向右区间找
left = middle + ;
} return -;
} // ====================测试代码====================
void Test(const char* testName, int numbers[], int length, int expected)
{
if (GetNumberSameAsIndex(numbers, length) == expected)
printf("%s passed.\n", testName);
else
printf("%s FAILED.\n", testName);
} void Test1()
{
int numbers[] = { -, -, , , };
int expected = ;
Test("Test1", numbers, sizeof(numbers) / sizeof(int), expected);
} void Test2()
{
int numbers[] = { , , , , };
int expected = ;
Test("Test2", numbers, sizeof(numbers) / sizeof(int), expected);
} void Test3()
{
int numbers[] = { -, , , , };
int expected = ;
Test("Test3", numbers, sizeof(numbers) / sizeof(int), expected);
} void Test4()
{
int numbers[] = { -, , , , };
int expected = -;
Test("Test4", numbers, sizeof(numbers) / sizeof(int), expected);
} void Test5()
{
int numbers[] = { };
int expected = ;
Test("Test5", numbers, sizeof(numbers) / sizeof(int), expected);
} void Test6()
{
int numbers[] = { };
int expected = -;
Test("Test6", numbers, sizeof(numbers) / sizeof(int), expected);
} void Test7()
{
Test("Test7", nullptr, , -);
} int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
Test7();
system("pause");
return ;
}