【通俗易懂二分查找法】——C语言实现

算法介绍

二分查找是一种针对有序数组（一种数据结构）的查找算法，在这样的数据结构中，对于查找某一特定的数值来说，二分法比线性查找要高效得多。

你小时候或许玩过这样一种猜谜游戏：我心里想着一个1到100之间的数字，在你猜出它之前，我会提示你的答案应该大一点还是小一点。你应该凭直觉就知道这个游戏的策略。一开始你会先猜处于中间的50，而不是1。为什么？因为不管我接下来告诉你更大或是更小，你都能排除掉一半的错误答案！如果你说50，然后我提示要再大一点，那么你应该会选75，以排除掉剩余数字的一半。如果在75之后我告诉你要小一点，你就会选62或63。
总之，一直都猜中间值，就能不断地缩小一半的范围。下面来演示这个过程，但仅以1到10为例。

这就是二分查找的通俗描述。有序数组相比常规数组的一大优势就是它除了可以用线性查找，还可以用二分查找。常规数组因为无序，所以不可能运用二分查找。

算法流程设计

1. 声明一个有N个元素的有序数组和一个要查找的数据值a。

2. 初始化两个边界值down=0索引，up=N-1索引，一个中间索引值T=(up+down)/2，然后比较数组[T]与a的大小，若a>数组[T]:则调整下界down=T+1，反之则调整上界up=T-1，直到down<=up这一条件不再满足，这里可以使用while循环语句。

（注：这里缩小范围的时候不要像我一样把注意力放在T上面，换个角度从边界处下手）

3. 若找到数组中存在数据值a，则返回其在数组中所在的位置，若没找到，则告知该数组中无此数据值。

算法实现

#include 

int main() {
	int orderArray[10] = {1,3,6,8,9,12,23,30,74,90};
    int a = 12;
    int down = 0;
    int up = 9;
    int T;
    while(down <= up){
        T = (down+up)/2;
        if(a == orderArray[T]){
            printf("The number %d is in this array and its index is %d",a,T);
            return 0;
        }else if(a < orderArray[T]){
            up = T-1;
        }else{
            down = T+1;
        }
    }
    printf("This number is not in this array!");
	return 0;
}

???这里的有序数组不知道是不是集合的一种，如果可以有重复值的话，要找出所有该值的位置就另当别论了，上面的程序只是在第一次找到该值就返回并结束，并没有判断是否有重复值。

有问题欢迎留言讨论~（虽然这个很简单，可能大家都会👀）