C语言二分查找在一个有序的数组中查找具体的数字

素颜马尾好姑娘i 2024-04-08 12:18 51阅读 0赞

## 二分查找 ##

### 在一个有序的数组中找具体的数字n ###

二分查找的使用条件：在有序的数组中查找；  
时间复杂度：log2n;  
譬如有232个数字，使用二分查找是非常快的，最多只需要查找32次。

**例如：给定1~10的数字找到7**

**数组的小标从0开始**

**代码中的sizeof是用来求数组大小的**

#include<stdio.h>
    int main()
    {
        
        int n=0;
        printf("请输入你要查找的数字:>");     //这里我们假设找数字7
        scanf("%d",&n);  
        int arr[10]={
        1,2,3,4,5,6,7,8,9,10};  //给定的数组
        int left=0;                          //定义左下标
        int riight = sizeof(arr)/sizeof(arr[0])-1; //定义右下标
        int mid=0;                          //定义中间值
        while(left<=right)
        {
        
            mid=(left+right)/2;
            if(n>arr[mid])
            {
        
                left =mid+1；
            }
            else if(n<arr[mid])
            {
        
                right=mid-1;
            }
            else
            {
        
                printf("%d",arr[mid]);
                break;
            }
        }
        return 0;
    
    }

代码 w h i l e 循环讲解 \\color\{red\}\{代码while循环讲解\} 代码while循环讲解:

![二分查找][708356b28a05400c8f1fe48365d07b0b.png_pic_center]

二分查找每次查找都会少一半的数字。  
当我们查找的数字比**mid**的值大,那么; l e f t = m i d + 1 , r i g h t 的值不变 \\color\{red\}\{left = mid+1,right的值不变\} left=mid\+1,right的值不变。

当我们查找的数字比**mid**的值小,那么; r i g h t = m i d − 1 , l e f t 的值不变 \\color\{red\}\{right = mid-1,left的值不变\} right=mid−1,left的值不变。

不论怎么查找，left向右走，right向左走，最终会相遇，两个下标相遇的时候，就是把所有的数都查找完了，要么找到，要么就是没有这个数字。

**学的不是技术，更是梦想。**

[708356b28a05400c8f1fe48365d07b0b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c282098d2c194e89b215b3485b570906.png