目錄
- 演算法概述
- 適用情況
- 演算法原理
- 演算法實作（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;
}
#endregion
#region 泛型
// 遞回版本
public static int RecursiveT<T>(T[] ary, T target) where T : IComparable
{
return RecursiveT(ary, 0, ary.Length - 1, target);
}
static int RecursiveT<T>(T[] ary, int low, int high, T target) where T : IComparable
{
if (high < low) return -1;
int mid = low + ((high - low) >> 1);
int cr = Comparer.Default.Compare(ary[mid], target);
if(cr==0)return mid;
if (cr > 0)
{
return RecursiveT(ary, low, mid - 1, target);
}
else
{
return RecursiveT(ary, mid + 1, high, target);
}
}
//While回圈版本
public static int WhileLoopT<T>(T[] ary, T target) where T : IComparable
{
int low = 0;
int high = ary.Length - 1;
while (low <= high)
{
int mid = low + ((high - low) >> 1);
int cr = Comparer.Default.Compare(ary[mid], target);
if (cr == 0) return mid;
if (cr>0)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1;
}
//默認情況下推薦使用While回圈版本
public static int DefaultT<T>(T[] ary, T target) where T : IComparable
{
return WhileLoopT(ary, target);
}
#endregion
}
測驗代碼如下：
//陣列必須有序
//此處用升序遞增的整數陣列是為了便于檢查結果
int[] ary = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
long[] aryT = new long[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
int target = 8;
int r = BinarySearch.Recursive(ary, target);
int w = BinarySearch.WhileLoop(ary, target);
int rT = BinarySearch.RecursiveT(ary, target);
int wT = BinarySearch.WhileLoopT(ary, target);
Console.WriteLine("r={0} w={1} rT={2} wT={3}", r, w, rT, wT);
實際應用：用二分查找法找尋邊界值
在集合中找到一個大于（小于）目標數t的數x，使得集合中的任意數要么大于（小于）等于x，要么小于（大于）等于t，
舉例來說：給予陣列和目標數
int array = {2, 3, 5, 7, 11, 13, 17};
int target = 7;
那么上界值應該是11，因為它“剛剛好”大于7；下界值則是5，因為它“剛剛好”小于7，
該問題不能直接使用二分查找的實作代碼解決，需要對代碼做一些修改，但解題思路還是二分查找，
實作代碼如下：
//用二分查找法找尋上界
static int BSearchUpperBound(int[] ary, int target)
{
int low = 0;
int high = ary.Length - 1;
while (low <= high)
{
int mid = low + ((high - low) >> 1);
if (high == low)
{
if (ary[mid] > target) return mid;
else return -1;
}
if (ary[mid] > target)
{
//當前找到的數大于目標數時，它可能就是我們要找的數，所以需要保留這個索引
high = mid ;
}
else
{
//當前找到的數小于等于目標數時繼續向上取區間
low = mid + 1;
}
}
return -1;
}
//用二分查找法找尋下界
static int BSearchLowerBound(int[] ary, int target)
{
int low = 0;
int high = ary.Length - 1;
while (low <= high)
{
//取中間索引時使用向上取整，否則low無法往上爬到下界值
int mid = low + ((high - low + 1) >> 1);
if (high == low)
{
if (ary[mid] < target) return mid;
else return -1;
}
if (ary[mid] >= target)
{
//當前找到的數大于等于目標數時繼續向下取區間
high = mid-1;
}
else
{
//當前找到的數小于目標數時，它可能就是我們要找的數，所以需要保留這個索引
low = mid;
}
}
return -1;
}
測驗代碼如下：
//尋找邊界值
int[] array =new int[]{ 2, 3, 5, 7, 11, 13, 17 };
int target =6;
//用二分查找法找尋上屆
int up = BSearchUpperBound(array, target);
int lo=BSearchLowerBound(array, target);
參考文章
二分搜索（Binary_Search）——簡書
binary search——百度百科
BinarySearch——.NET原始碼
二分查找BinarySearch原理分析、判定樹、及其變種——CSDN
二分查找法的實作和應用匯總——CSDN
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/1623.html
標籤：C#
上一篇：設計模式之配接器模式