在计算机科学中,折半搜索,也称二分查找算法、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 复杂度分析 时间复杂度折半搜索每次把搜索区域减少一半,时间复杂度为。(n代表集合中元素的个数)空间复杂度 。虽以递归形式定义,但是尾递归,可改写为循环。
#include<stdio.h> #include<string.h> #include<math.h> #include<ctype.h> #include<stdbool.h> #define COMPARE(x,y) (((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1) /* int COMPARE(int x, int y) { if(x < y) { return -1; } else if(x == y) { return 0; } else { return 1; } } */ /* 非递归代码 */ int binsearch(int list[], int searchchnumm, int left, int right) { int middle; while(left <= right) { middle = (right + left)/2; switch(COMPARE(list[middle], searchchnumm)) { case -1: left = middle + 1; break; case 0: return middle; break; case 1: right = middle -1; break; default: break; } } return -1; } /* 递归代码 */ int binsearch(int list[], int searchchnumm, int left, int right) { int middle; if(left <= right) { middle = (left + right)/2; switch(COMPARE(list[middle], searchchnumm)) { case -1: return binsearch(list, searchchnumm, middle + 1, right); break; case 0: return middle; break; case 1: return binsearch(list, searchchnumm, left, middle - 1); break; default: break; } } return -1; } int main() { int list[] = {2,4,5,1,-3,6,8,10,55,23}; int searchnum = 5; int length; length = sizeof(list) / sizeof(int); printf("%d\n",length); printf("%d\n",binsearch(list,searchnum,0,length)); return 0; }
相关推荐
折半查找算法在顺序表中插入一个元素讲解.pdf
静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法静态查找表。实现有序表的折半查找算法
用C语言实现折半查找,折半查找算法较简单
折半查找算法 顺序表 折半查找算法C语言版
该算法是在折半算法的基础上,推广折段的段数,通过简单的数学模型证明了最优的分段数为3,而不是2(即折半)。在文章的最后给出了算法的C程序代码。如果有应用到实际中,算法还可以进一步精简。
折半查找算法,折半查找算法,折半查找算法
递归调用的折半查找java代码,算法分析与设计实验报告。
折半查找法是数据结构与算法的应用中相对重要的一个查找方法。还可以通过数学方法计算其时间复杂度。
查找问题(顺序查找法, 折半查找法,)基本思想:一列数放在数组a(1)---a(n)中,待查找的数放在x 中,把x与a数组中的元素从头到尾一一进行比较查找。用变量p表示a数组元素下标,p初值为1,使x与a(p)比较,如果x不等于a...
递归折半查找法基本的程序思想,初学者可以参考一下。
public int searchNumber(double num, boolean updown) {// 折半查找算法 int left = 0, right = Array.length - 1, middle = -1; while (left ) { middle = (left + right) / 2; if (num == Array[middle]) ...
本书是折半查找算法的标准教材,目的是让大家知道好的程序设计和算法分析技巧,难得一见的好书!
折半查找的基本算法是:每次查找前先确定数组中待查的范围:low和high(low),然后把m于中间位置(mid)中元素的值进行比较。如果m的值大于中间位置元素中的值,则下一次的查找范围落在中间位置之后的元素中;反之,下一...
在数组x中查找数字a,其中x是一个元素各异并按升序排列的一维数组.若找到a,则返回a在x中的位置,若a不在x中则返回“找不到”.
java 快速排序 折半查找的界面实现 (递归与分治法)
使用折半查找,输入一个整数,查找是否在数组中,如在给出下标,否则-1
数据结构中的折半查找程序,C语言描述,数据结构中的折半查找程序,C语言描述
西工大C 毕设论文:折半查找法演示器,里面包括了一个毕业论文的模板,本程序演示的功能是折半查找法,测试时请输入你想要查找数据的数据表列的数据个数(1--50),还需要输入你要在其中查找数据的数据表列(%d个数据...
在上述代码中,`binarySearch`函数实现了折半查找算法。通过维护两个指针`left`和`right`来确定当前的查找范围。在每一次循环中,计算中间元素的索引`mid`,然后用目标值与中间元素进行比较。如果相等,说明找到了...