【愚公系列】2021年11月 C#版 資料結構與算法解析(二分查找)

二分查找也稱折半查找，它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。 首先，假設表中元素是按升序排列，将表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄将表分成前、後兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重複以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

示例

public class Program {

   public static void Main(string[] args) {

       int[] array = { 8, 11, 21, 28, 32, 43, 48, 56, 69, 72, 80, 94 };

       Console.WriteLine(BinarySearch(array, 80));

       Console.WriteLine(BinarySearch(array, 66, 0, array.Length - 1));

       Console.ReadKey();

   }

   private static int BinarySearch(int[] array, int key) {

       //直接求解

       var min = 0;

       var max = array.Length - 1;

       var mid = 0;

       while (min <= max) {

           mid = (min + max) >> 1;

           if (array[mid] > key) {

               max = mid - 1;

           }

           else if (array[mid] < key) {

               min = mid + 1;

           else if (array[mid] == key) {

               return mid;

           }  

       }

       return -1;

   private static int BinarySearch(int[] array, int key, int low, int high) {

       //遞歸法

       if (low > high) return -1;

       var mid = (low + high) >> 1;

       if (array[mid] > key)

           return BinarySearch(array, key, low, mid - 1);

       else if (array[mid] < key)

           return BinarySearch(array, key, mid + 1, high);

       else

           return mid;

}

請注意以上遞歸實作為尾遞歸：盡量使用尾遞歸

在最壞的情況下，二分查找需要在最後一次才能查找到目标關鍵字，假設原問題規模為n，每次折半原問題，設在第k次時問題規模變為1，那麼令 2^k=1 ，因為指數和對數互為逆運算，解得 k=log_{2}n ，即二分查找在最壞的情況下的時間複雜度為： O(logn) 。