2020-07-25

简单实用算法——二分查找法(BinarySearch)

二分查找(英语:binary search),也叫折半查找(英语:half-interval search),是一种在有序数组中查找特定元素的搜索算法。所以,二分查找的前提是数组必须是有序的。二分查找只适用顺序存储结构。为保持表的有序性,在顺序结构里插入和删除都必须移动大量的结点。因此,二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。对那些查找少而又经常需要改动的线性表,可采用链表作存储结构,进行顺序查找。链表上无法实现二分查找(更准确的说链表上使用二分查找得不偿失)。

目录

  • 算法概述
  • 适用情况
  • 算法原理
  • 算法实现(C#)
  • 实际应用:用二分查找法找寻边界值
  • 参考文章

算法概述

二分查找(英语:binary search),也叫折半查找(英语:half-interval search),是一种在有序数组中查找特定元素的搜索算法。所以,二分查找的前提是数组必须是有序的。
时间复杂度、空间复杂度请参照下图(图片来自wikipedia):

适用情况

二分查找只适用顺序存储结构。为保持表的有序性,在顺序结构里插入和删除都必须移动大量的结点。因此,二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表

对那些查找少而又经常需要改动的线性表,可采用链表作存储结构,进行顺序查找。链表上无法实现二分查找(更准确的说链表上使用二分查找得不偿失)

算法原理

二分查找的基本思想是:

  • R[low…..high]是当前的查找区间
  • 首先确定该区间的中点位置:mid = low + ((high - low) >> 1)
  • 然后将待查的target值与ary[mid]比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找。
  • 若ary[mid]>target,则由表的有序性可知ary[mid….high]均大于K,因此若表中存在关键字等于target的结点,则该结点必定是在位置mid左边的子表R[low…mid-1]中,故新的查找区间是左子表ary[low…...mid-1]
  • 若ary[mid]<target,则要查找的target必在mid的右子表ary[mid+1……high]中,即新的查找区间是右子表ary[mid+1……high]
  • 下一次查找是针对新的查找区间进行的。

因此,从初始的查找区间R[0..n-1]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为target的结点,或者直至当前的查找区间为空(high<low,即查找失败)时为止。

算法实现(C#)

算法基于C#编写,有简单和泛型两种实现,每种实现又分递归版本、While循环版本。实际运用时,推荐使用While循环版本的二分查找
算法代码如下:

 //此算法假定数组已排序;如果不是这样,则结果将不正确。 class BinarySearch {  //不要使用mid = (high + low) / 2,可能会导致运算溢出  #region 简单  // 递归版本     public static int Recursive(int[] ary, int target)  {   return Recursive(ary, 0, ary.Length-1, target);     }  static int Recursive(int[] ary, int low, int high, int target)  {   if (high < low) return -1;    int mid = low + ((high - low) >> 1);   if (ary[mid] == target) return mid;   if (ary[mid] > target)   {    return Recursive(ary, low, mid-1, target);   }   else   {    return Recursive(ary, mid + 1, high, target);   }     }  //While循环版本  public static int WhileLoop(int[] ary, int target)  {   int low = 0;    int high = ary.Length - 1;   while (low <= high)   {            int mid = low + ((high - low) >> 1);    if (ary[mid] == target) return mid;    if (ary[mid] > target)    {     high = mid - 1;    }    else     {     low = mid + 1;    }   }   return -1;  }  

No comments:

Post a Comment