c语言实现二分查找

雨点打透心脏的1/2处 2022-07-03 13:28 257阅读 0赞

二分查找又称折半查找，优点是比较次数少，查找速度快，而其缺点是要求待查找为有序排列的。

其基本原理是将一组n个数分为两半，取arr\[n/2\]与待查找的数x比较，若arr\[n/2\]<x，我们只需在数组arr的右半部分继续查找，反之，则在左半部分继续查找，直至x=arr\[n/2\],算法终止。

下例为在1-10的数组arr中找一个指定的数字，找到输出数字下标，否则输出找不到。

#include <stdio.h>  
    int binary_search(int arr[10], int key, int left,int right)  
    {  
        while (left <= right)  
        {  
            int mid = left + ((right - left) >> 1);  
            if (arr[mid] < key)  
                left = mid + 1;  
            else if (arr[mid] > key)  
                right = mid - 1;  
            else   
                return mid;  
        }  
        return -1;  
    }

int main()  
    {  
        int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };  
        int key = 5;  
        printf("请输入要查找的数：");  
        scanf("%d", &key);  
        int sz = sizeof(arr) / sizeof(arr[0]);  
        int ret = binary_search(arr, key, 0, 9);  
        if (ret == -1)  
            printf("找不到\n");  
        else  
            printf("arr[%d]\n",ret);  
        return 0;  
    }

运行结果：

![SouthEast][]

[SouthEast]: /images/20220618/1859f6d515a0483aa5ba321e69551538.png

发表评论取消回复

表情：

评论列表（有 0 条评论，257人围观）

还没有评论，来说两句吧...

相关阅读

相关 C语言实现二分查找

include<stdio.h> define N 10 int main(){ int a[N]={ 1,2,3,4,5,6,7,8,9,

爱被打了一巴掌/ 2023年07月16日 13:58/ 0 赞/ 27 阅读

相关二分查找 c语言实现

提到二分查找，相信很多人都不陌生，大学学数据结构的时候老师都讲过，它是一种效率较高的查找方法，基于顺序存储结构的线性表，且要求表中元素按关键字有序排列。假设元素非递减排列，则常

桃扇骨/ 2023年06月18日 13:54/ 0 赞/ 24 阅读

相关二分查找/折半查找——C语言实现

折半查找的应用前提是数组是一个有序数组。比较数组中间值和查找值的大小关系，然后确定下一步的查找范围，逐次缩小。折半查找的时间复杂度为O(log2(n))，是一种效率很高的查找方

ゝ一世哀愁。/ 2023年06月03日 02:58/ 0 赞/ 44 阅读

相关顺序查找和二分查找，C语言实现

这一章节将讲解查找算法，包括顺序查找、二分查找。其中二分查找是通向编程高手路上的十大算法中的一种。 1 顺序查找虫虫和东东是兄弟俩，经常一起做游戏。这次他们玩的是猜数

灰太狼/ 2023年03月01日 05:43/ 0 赞/ 60 阅读

相关二分查找法(C语言实现)

include <stdio.h> include <stdlib.h> int BinarySearch(int arr[],int n,i

Dear 丶/ 2023年02月14日 10:39/ 0 赞/ 26 阅读

相关 c语言实现二分查找

二分查找又称折半查找，优点是比较次数少，查找速度快，而其缺点是要求待查找为有序排列的。其基本原理是将一组n个数分为两半，取arr\[n/2\]与待查找的数x比较，

雨点打透心脏的1/2处/ 2022年07月03日 13:28/ 0 赞/ 258 阅读

相关 c语言实现二分查找

include<stdlib.h> include<stdio.h> int BinarySearch(int arr,int x,int length

朴灿烈づ我的快乐病毒、/ 2022年05月17日 03:17/ 0 赞/ 254 阅读

相关二分查找（C语言）

include <stdio.h> include <stdlib.h> int BinarySearch(int array,int key

本是古典何须时尚/ 2021年12月11日 13:51/ 0 赞/ 345 阅读

相关二分查找（c语言实现）

题目本题要求实现二分查找算法。函数接口定义： Position BinarySearch( List L, ElementType X ); 其中

淩亂°似流年/ 2021年11月16日 06:46/ 0 赞/ 465 阅读

相关二分查找法c语言实现

二分查找法是从已经排序的线性表（通常是数组）里快速查找到目标元素所在索引，时间复杂度O(log2n)。以下是从java源代码中抄来，稍微修改的代码。 includ

本是古典何须时尚/ 2021年10月13日 16:51/ 0 赞/ 394 阅读