本页使用了标题或全文手工转换

折半搜索算法

维基百科,自由的百科全书
跳转至: 导航搜索

计算机科学中,折半搜索,也称二分查找算法二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

复杂度分析[编辑]

时间复杂度
折半搜索每次把搜索区域减少一半,时间复杂度为O\left( \log n  \right)。(n代表集合中元素的个数)
空间复杂度
O\left(  1  \right)。虽以递归形式定义,但是尾递归,可改写为循环。

应用[编辑]

除直接在一个数组中查找元素外,可用在插入排序中。

示例代码[编辑]

//递归版本
int binary_search( const int arr[], int low, int high, int key)
{
   int mid = low + (high - low) / 2; // Do not use (low + high) / 2 which might encounter overflow issue
   if (low > high)
       return -low - 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, mid+1, high, key);
     }
}

参考[编辑]

本条目的部分内容翻译自英語維基百科条目Binary search algorithm並以知识共享-署名-相同方式共享3.0协议授权使用。原文作者列表請參閱其页面历史
  • Sahni, Sartaj. Data Structures, Algorithms, and Applications in C++. McGraw2-Hill. 1998. ISBN 978-0072362268. 

外部链接[编辑]