折半搜索算法
维基百科，自由的百科全书
（重定向自二分查找算法）
在计算机科学中，折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
目录 |
[编辑] 复杂度分析
- 时间复杂度
- 二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为
。（n代表集合中元素的个数） - 空间复杂度
。虽以递归形式定义，但是尾递归，可改写为循环。
。（n代表集合中元素的个数）
。虽以递归形式定义，但是[编辑] 应用
除直接在一个数组中查找元素外，可用在插入排序中。
[编辑] 示例代码
int half_seek(int arr[], int low, int high, int num) { if((low>=high)&&(arr[low]!=num)) return -1; int mid; mid = (low+high)/2; if(arr[mid]==num) return mid; else if(arr[mid]>num) high = mid-1; else low = mid+1; return half_seek(arr,low,high,num);//递归 }
[编辑] 参考
- 本条目的部分内容翻译自英語維基百科条目Binary search algorithm並以知识共享-署名-相同方式共享3.0协议授权使用。原文作者列表請參閱其页面历史。
- Sahni, Sartaj. Data Structures,Algorithms,and Applications in C++. McGraw2-Hill. 1998. ISBN 978-7-11-07645-2.
