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语言程序设计:二分查找(折半查找)

C语言程序设计:二分查找(折半查找)

1.什么是二分查找

二班查找又称折半查找,他是一种高效率的查询方法。

2.二分查找的优点

高效,减少查询次数,查找的速度快,平均性能好(貌似 快速排序 也是),非递归实现(我觉得也是优点吧)。

3.二分查找的缺点

1)必须采用顺序存储结构。

2)必须按关键字大小有序排列。

说人话就是 数据得是数组,且从大到小 或者 从小到大 等进行排好序。

4.二分查找原理

1

针对已经排列好的数组,假如我判断6是否在这个数组内,如果是返回ture,否则返回false。

我们在数组的最左边定义一个left,在最右边定义为right,中间的mid则为(left+right)/2

我们用mid的值与6做对比,发现mid的值为5,6比5大,则mid左边的所有数据都抛弃掉,同时,我们把left的值设为mid+1,right保持不变

NueXini2

则left则到了6这个位置,则mid可以是7或者8这个位置,不影响操作。假设mid在的7位置

我们这时在比较6与mid的值比较,发现mid的值为7,6比7小,则mid右边的所有数据都抛弃掉,同时right变为mid-1

NueXini3.png

此时,我们的mid位置为(left+right)/2=6,mid的第6位置的值为6,是我们要查找的6,则 return true。


但是,假如我们查找的数不在这个数组里面呢?

首先,我们定义一串这样的数组a,要查找的数为60

NueXini4

定义a起始位置为left,末尾位置为right,则mid=(0+9)/2=4(4或者5都可以),a[mid]=a[4]=45

60比a[mid]=45大,所以我们可以舍弃mid左边所有的数据,同时,left=mid+1即left=5,right不变

NueXini5

此时mid=(left+right)/2=(5+9)/2=7,a[mid]=a[7]=74

同理,60小于74,则right=mid-1=6,left不变

NueXini6

此时只剩下两个值,mid=(5+6)/2=5或6,mid等于哪个都没问题,a[mid]=a[6]=67,我们要找的值是60,那我们继续分析的话,则right=mid-1,那left=mid=right,假如我们要找的数是67,我们就找到了,返回true,可惜我们现在找的是60,在走下去,依旧得不到结果,这样做就没有意义了,所以要使它有意义就必须满足left<=right,这便是我们进行二分查找的循环条件~~!

5.源代码实现

#include<stdbool.h>
#include<stdio.h>

bool halfsort(int need_num, int num[], int num_length);

int main()
{
	int a[] = { 11,18,22,34,45,53,67,74,89,99 };
	int len = sizeof(a) / sizeof(a[0]);
	for (int i = 0; i < len; i++)
	{
		printf("正在检测[%d]:%d\n", a[i], halfsort(a[i], a, len));
	}
	
}

bool halfsort(int need_num, int num[], int num_length)
{
	bool ret = false;
	int left = 0;
	int right = num_length - 1;//计算出数组个数,数组中下标从0开始,需要-1
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (num[mid] == need_num) {
			ret = true;
			break;
		}
		else if ( need_num < num[mid]) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}

	}
	return ret;
}

6.后话

分析原理的时候,可能说的有点乱,大概就是那样子,可以自己琢磨分析一下,enioy it~

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-12-15 18:33:00  更:2021-12-15 18:34:12 
 
开发: 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 16:53:35-

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