如何在一串有序数组里找到一个元素的下标呢？

例如 在 arr [ ] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } 里找到 4 的下标。

我们可能第一时间就想到了一个最简单的方法，从头到尾一个一个对比，相同则打印下标。

但是效率是不是太低了呢？

“你猜我这车多少钱买的？”

“1块？”

“不是”

“两块？“

“......”

等猜对了哥们都换新车了 

这个时候就能体现出二分查找的效率所在

所谓二分查找就是每次都排除一半，快速缩小搜寻范围。

例如 我们要从 有序数组 arr [] =  { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 }  中找到数字 7 的下标

 

 

我们产生一个思路

先找到最中间的那个数 arr[4] ,也就是 5 。然后判断 5 比 7大还是小，5 比 7 小，则把arr[0]-arr[4]直接筛除，缩小一半查找范围。

 

 

然后继续找到中间的数arr[7]，也就是8。再判断 8 和 7 的大小关系，8 比 7 大，则将arr[9]-arr[10]筛掉，再次缩短一半的范围。

 

 

 

 这样我们的搜索范围只剩下 6 和 7由此可见，效率十分之高。

那么怎么用代码来实现呢？

首先 我们定义，所查找的数组范围中

最小值的的下标为left，最大值下标为right。即 arr[left] , arr[right]。中间值为arr[mid]

那么初始left的值我们知道是0，那right是多少呢

我们用数组总大小除以单个数组大小 就可以得到数组内元素数量，也就是

right = sizeof(arr)  / sizeof(arr[0])  - 1       // -1是因为数组的下标从0开始

那么中间值mid 为

mid = ( left + right ) / 2

开始写代码    比如我们要在数组 arr 中找到7的下标。

首先，我们要在数组中找到中间的元素 arr[mid],由刚才的总结得知 mid = ( left + right ) / 2

#include<stdio.h>
int main ()
{    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };int a = 7;int left = arr[0];int right = arr[sizeof(arr)  / sizeof(arr[0])  - 1 ];int mid = ( left + right ) / 2;return 0;
}

当我们取得了中间值，我们要判断中间值和我们要找的值的大小关系。

如果比要找的值大，那就把小的那一半筛掉，反之亦然。如果相同那就说明我们找到了数字。

#include<stdio.h>
int main ()
{    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };int a = 7;int left = arr[0];int right = arr[sizeof(arr)  / sizeof(arr[0])  - 1 ];int mid = ( left + right ) / 2;if(arr[mid] > a){right = mid - 1 ;// -1 的作用是因为 arr[mid] 本身就不是要找的值，所以一起筛掉。}else if(arr[mid] < a){left = mid + 1  ;// +1 的作用同上}else{printf("找到了，下标为 %d", mid);break;}return 0;
}

如此一来我们就筛掉了一半的搜索范围，但我们还并未找到，所以我们要进一步缩小。

当我们想要重复筛选时，则要将代码写入循环,同时给一个条件。

因为范围一直在缩小，当 left 和 right 相互交错的时候就说明已经没有范围可以缩小了，搜索已经结束了，如果仍然没有打印下标，那就说明没找到。所以我们得到结论 left 和 right 在未交错的情况下才继续寻找 a 的下标，如果 left 和 right 交错还没找到，那么打印 没找到

在代码中实现：

#include<stdio.h>
int main ()
{    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };int a = 7;int left = arr[0];int right = arr[sizeof(arr)  / sizeof(arr[0])  - 1 ];while(left<=right){int mid = ( left + right ) / 2; //此行务必放入循环内部if(arr[mid] > a)                //因为中间值每次循环都要重新赋值{right = mid - 1 ;}else if(arr[mid] < a){left = mid + 1  ;}else{printf("找到了，下标为 %d", mid);break;}}if ( left > right )printf("没找到");return 0;
}

打印结果：  找到了，下标为 6