二分查找（英語：binary search），也叫折半查找（英語：half-interval search），是一種在有序數組中查找特定元素的搜索演算法。所以，二分查找的前提是數組必須是有序的。二分查找只適用順序存儲結構。為保持表的有序性，在順序結構里插入和刪除都必須移動大量的結點。因此，二分查找特... ...

演算法概述

二分查找（英語：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;
}