小白的崛起之路——每日一记

方法：二分法    题目 ：编写代码在一个整形有序数组中查找具体的某个数            

                         要求：找到了就打印数字所在的下标，找不到则输出：找不到。

对于查找一个数字，首先肯定会想到把这些数字全部找一遍，而这样不仅费时又费力，这时二分法的好处就体现出来了。什么是二分法呢？，在数学中就是对于区间[ a , b ]上连续不断且f（a）·f（b）<0的函数y=f（x）。通过连续不断的把零点所在区间一分为二，不断缩小范围，使两个端点逐步逼近零点，进而得到近似于零点的值方法叫做二分法。

而在c语言中二分法适用于当数据量很大，并且是有序序列中。

什么原理呢。设置一个arr数组来存放数列，定义三个变量，left（left为最左边的下标）， right（left为最右边的下标）， mid（mid为左右下标的中间值mid=left+(right-left)/2），如果比如这个序列为1，2，3，4，5，6，7，8，9，10；你想找到一个数key=7；

如果arr[mid]是小于key，那说明key还在右边这时数据范围就缩小到[mid+1,right],(mid为什么要加一呢？因为mid所占的数据不符所以要加一缩小范围）。也就是把mid+1的值赋给了left；然后再算出mid值进行查找，如果下一次arr[mid]==key 那恭喜找到了，否则继续进行以上操作，也就可以放进一个循环中，当[left,right]区间不断缩小里面的元素也就不断减小，直到元素没有为止循环停止。这时如果left大于right说明这个序列中没有想要找的元素key。

如果arr[mid]是大于key，那说明key还在左边这时候数据范围就缩小到[right,mid-1]也就是把mid-1的值赋给了right。(道理如上）

#include <stdio.h>
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    int left = 0;
    int right = sizeof(arr) / sizeof(arr[0]) - 1;
    int key = 7;
    while (left <= right)//判断left和right之间还有没有元素在，
        //否则继续，直到区间中没有元素时，说明key不在集合中，打印找不到
    {
        int mid = left + (right - left) / 2;/
        if (arr[mid] < key)
            left = mid + 1;
        else if (arr[mid] > key)
            right = mid - 1;
        else
        {
            printf("%d", mid);
            break;
        }
    }
    if (left > right)
    {
        printf("找不到了");
    }
    return 0;
}