// 面試題53（三）：數(shù)組中數(shù)值和下標(biāo)相等的元素 // 題目：假設(shè)一個(gè)單調(diào)遞增的數(shù)組里的每個(gè)元素都是整數(shù)并且是唯一的。請(qǐng)編程實(shí) // 現(xiàn)一個(gè)函數(shù)找出數(shù)組中任意一個(gè)數(shù)值等于其下標(biāo)的元素。例如，在數(shù)組{-3, -1, // 1, 3, 5}中，數(shù)字3和它的下標(biāo)相等。//思想：因?yàn)檫@里也是遞增的，如果中間點(diǎn)的值大于下標(biāo)，那后面所有值都會(huì)大于相應(yīng)下標(biāo)，同理中間點(diǎn)小于下標(biāo)，前面都會(huì)小于下標(biāo) #include <iostream>int GetNumberSameAsIndex(const int* numbers, int length) {if (numbers == nullptr || length <= 0)return -1;int left = 0;int right = length - 1;while (left <= right){int middle = left + ((right - left) >> 1);if (numbers[middle] == middle)//第一種情況，中間點(diǎn)直接中了return middle;if (numbers[middle] > middle)//第二種情況，中間點(diǎn)值大于坐標(biāo)，向左區(qū)間找right = middle - 1;else//第三種情況，中間點(diǎn)值小于坐標(biāo)，向右區(qū)間找left = middle + 1;}return -1; }// ====================測(cè)試代碼==================== void Test(const char* testName, int numbers[], int length, int expected) {if (GetNumberSameAsIndex(numbers, length) == expected)printf("%s passed.\n", testName);elseprintf("%s FAILED.\n", testName); }void Test1() {int numbers[] = { -3, -1, 1, 3, 5 };int expected = 3;Test("Test1", numbers, sizeof(numbers) / sizeof(int), expected); }void Test2() {int numbers[] = { 0, 1, 3, 5, 6 };int expected = 0;Test("Test2", numbers, sizeof(numbers) / sizeof(int), expected); }void Test3() {int numbers[] = { -1, 0, 1, 2, 4 };int expected = 4;Test("Test3", numbers, sizeof(numbers) / sizeof(int), expected); }void Test4() {int numbers[] = { -1, 0, 1, 2, 5 };int expected = -1;Test("Test4", numbers, sizeof(numbers) / sizeof(int), expected); }void Test5() {int numbers[] = { 0 };int expected = 0;Test("Test5", numbers, sizeof(numbers) / sizeof(int), expected); }void Test6() {int numbers[] = { 10 };int expected = -1;Test("Test6", numbers, sizeof(numbers) / sizeof(int), expected); }void Test7() {Test("Test7", nullptr, 0, -1); }int main(int argc, char* argv[]) {Test1();Test2();Test3();Test4();Test5();Test6();Test7();system("pause");return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/CJT-blog/p/10538096.html

總結(jié)

以上是生活随笔為你收集整理的《剑指offer》第五十三题（数组中数值和下标相等的元素）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。