问题描述

有一数组，数组中相邻两个元素之间的差值为1，例如table数组：[2, 3, 4, 5, 4, 5, 6, 7, 8, 9] ,给定某个数，如何最快定位该数第一次出现的位置。

思路

我们要充分利用“相邻元素之间的差值为1”这个条件。假设我们要查找“7”这个元素，将table[0]与”7″比较，由于table[0]的值为2，不相等。此时我们要比较的下一个元素是table[ abs(2-7) ]，即table[5]。理由是，由于相邻元素的差值为”1″,所以最快的增长方式是每个元素都比前一个元素大1(同理，最快的减小方式是每个元素都比前 一个元素小1)，当前的元素是2，查找的元素是7，按最快的增长方式的话，也要等到table[5]的时候才能达到7，所以直接将table[5]与7比较。
即当前的元素的table[i],如果table[i]等于要查找的元素target,查找成功。否则的话，就将table[abs(table[i] – target)]与target比较，循环进行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* @file   search.c
* @author pein <pein0119@gmail.com>
* @date   Fri Sep 13 17:31:31 2013
* 
* @brief  给定一个数，找出该数在数组中第一次出现的位置
* 
* 
*/
#include <stdio.h>
#include <math.h>

#define TABLELENGTH 10
int main(int argc, char *argv[]) 
{
    int i, target;
    int table[TABLELENGTH] = {
        2, 3, 4, 5, 4, 5, 6, 7, 8, 9
    };

    printf ("请输入要查找的数：\n");

    scanf("%d", &target);

    i = 0;
    while(i < TABLELENGTH)
    {
        if(table[i] == target) 
        break;

        /* 核心部分 */
        i += abs(table[i] - target);
     }

    if (i >= TABLELENGTH)
        printf ("查找失败！\n");
    else
        printf ("%d 第一次出现的位置为： %d\n", target, i);

    return 0;
}

运行结果