IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 二分查找算法的实现(C语言) -> 正文阅读

[数据结构与算法]二分查找算法的实现(C语言)

在计算机科学中,二分查找(英语:binary search),也称折半查找(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从的数组中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

?从上面的简介可以看出,使用二分查找算法的条件有二:

1,有序。2,元素顺序存储,即数组

二分查找的重要思想在于,找到中间的数,将其与左右两边的“界限”做比较,从而再次缩小左右两边的界限,直到找到我们所要的那个元素。

在数组中找一个数,我们最容易想到的就是将其与数组中每一个数作比较,代码实现如下

#include<stdio.h>
int main()
{
   int arr[10]={1,2,3,4,5,6,7,8,9,10};
   int k=0;
   scanf("%d",&k);
   int i=0;
   for(;i<10;i++)
   {
     if(arr[i]==k)
     break;
   }
  if(i<10)
   printf("找到了:下标是%d\n",i);
  else
   printf("找不到");
   return 0;
}

而这样去查找很显然,当要查找的元素在数组的后面时,所消耗的时间会需要很多,这处的例子数组元素较少,而之后若数组元素增大呢?

而二分查找算法就极大提高了查找的效率,每次查找完 都可以排除掉一半的元素,代码实现如下

#include<stdio.h>
int main()
{
	int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int sz = sizeof(arr) / sizeof(arr[0]);//求数组元素个数
	int k = 0;
	scanf("%d", &k);//输入所要查找的数
	int left = 0;//左界限
	int right = sz-1; //右界限
	while (left <= right)//确保两者之间还有元素可以查找
	{
		int mid = (left + right) / 2;
		if (arr[mid]<k)
			left = mid+1;
		else if (arr[mid]>k)
			right = mid-1;
		else
		{
			printf("找到了,下标是:%d\n", mid);
			break;
		}
	}
	if (left>right)
		printf("找不到\n");
	return 0;
}

记得要用break跳出循环,否则会一直打印。以上就是二分查找算法的实现。

这时候有个问题了,不是顺序的数组怎么办,我又想用二分查找算法来找元素。这个就涉及到排序算法啦,排序算法有多种,之后的博客在慢慢跟大家分享。希望对大家的学习有所帮助。看到这里,不妨点个关注吧,我会坚持更新的。

以上内容,如有错误,请联系修改。

参考资料:

1,二分搜索算法_百度百科 (baidu.com)

2,二分查找算法动图 - 国内版 Bing images(图片来源)

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-10-11 17:45:19  更:2021-10-11 17:45:25 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 6:29:37-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码