折半搜索算法

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

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

复杂度分析[编辑]

时间复杂度
折半搜索每次把搜索区域减少一半,时间复杂度为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 -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. 

外部链接[编辑]