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