C语言中的折半查找法是什么
来源:百度文库 编辑:神马文学网 时间:2024/04/28 12:06:41
折半查找的前提是已经对数据做好了排序,然后再折半查找
例如排序后的数据是1 5 12 35 64 78 89 123 456
你要查找12,首先用12跟上面排好顺序的9个数中间那个比较(64),12<64,因此你查找的数据在前半部分,即
1 5 12 35 64,再用12跟前半部分中间那个数比较(12),这样找了2次就找到了
折半查找的目的是提高查找的效率 折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。
【基本思想】
将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果xa[n/2],则我们只要在数组a的右半部继续搜索x。
二分搜索法的应用极其广泛,而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了,但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing Correct Programs》中写道,90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定,正确地归纳奇偶数的各种情况,其实整理后可以发现它的具体算法是很直观的。 刚开始的时候数组时排好顺序的:从小到大,或者从大到小。然后将这个数组折中,用中间的这个数和要查找的数比较大小,(例如:如果我从小到大,我将数组这种后,用中间的数和要查找的数比较,如果小,则那个要查找的数绝对在中间靠左的范围里,如果大,则那个要查找的数绝对在中间靠右的范围里,然后同理,慢慢慢慢缩小范围,知道查找到为止)
例如排序后的数据是1 5 12 35 64 78 89 123 456
你要查找12,首先用12跟上面排好顺序的9个数中间那个比较(64),12<64,因此你查找的数据在前半部分,即
1 5 12 35 64,再用12跟前半部分中间那个数比较(12),这样找了2次就找到了
折半查找的目的是提高查找的效率 折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。
【基本思想】
将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果xa[n/2],则我们只要在数组a的右半部继续搜索x。
二分搜索法的应用极其广泛,而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了,但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing Correct Programs》中写道,90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定,正确地归纳奇偶数的各种情况,其实整理后可以发现它的具体算法是很直观的。 刚开始的时候数组时排好顺序的:从小到大,或者从大到小。然后将这个数组折中,用中间的这个数和要查找的数比较大小,(例如:如果我从小到大,我将数组这种后,用中间的数和要查找的数比较,如果小,则那个要查找的数绝对在中间靠左的范围里,如果大,则那个要查找的数绝对在中间靠右的范围里,然后同理,慢慢慢慢缩小范围,知道查找到为止)
递归,分治,思想
将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果xa[n/2],则我们只要在数组a的右半部继续搜索x
C语言中的折半查找法是什么
C语言中的break
解析C语言中的sizeof
解析C语言中的sizeof
C语言中的多级指针
OO in C-C语言中的面向对象思想
c语言在串中查找第一个给定字符集内容的段函数
c语言在串中查找指定字符集的子集的第一次出现函数
c语言
c语言
c 语言
c语言
c语言
c语言
C语言
感触c语言中的面向对象思想 2
c语言结构体中的冒号的用法
C语言中在一个串中查找给定字符的第一个匹配之处函数
OO in C(1): C语言中的类模拟和多态,继承
OO in C(1): C语言中的类模拟和多态,继承
[编程技巧]C语言的学法
c语言把串中的一部分与另一串中的一部分比较, 不管大小写函数
怎样查找会计核算中的错误
C语言学习方法