C#實現折半查找算法
折半查找,也叫二分查找,當在一個數組或集合中查找某個元素時,先定位出中間位置元素,如果要查找的元素正好和該中間位置元素相等,通過一次查找,就能找到匹配元素;如果要查找的元素小於該中間位置元素,就拋棄後面一半的元素,在前面一半的元素中再定位出中間位置元素,如此反復,直到找到匹配元素;如果要查找的元素大於該中間位置元素,就拋棄前面一半的元素,在後面一半的元素中定位出中間位置元素,如此反復。
面臨的第一個問題是:中間位置元素如何定位?在折半查找中規定:當元素個數是奇數,比如有3個元素,中間位置元素是索引為1的元素;當元素個數是偶數,比如有4個元素,索引為1和2的元素理論都是中間位置元素,但在折半查找中,把後面這個,即索引為2的元素視為中間位置元素。
面臨的第二個問題是:由於,要查找的元素和中間位置元素之間需要比較,我們在比較之前,勢必要讓數組按升序或降序來排列。
自定義一個類,該類維護著一個int[]類型數組,通過構造函數確定數組長度和對數組進行排序,並提供打印數組元素的方法,以及折半算法。
public class MyArray { private int[] arr;//內部維護著一個數組 private static Random r = new Random();//用它來生成數組的隨機元素 //通過構造函數來確定內部數組的長度,並生成數組的隨機元素,並對數組元素排序 public MyArray(int size) { arr = new int[size]; for (int i = 0; i < size; i++) { arr[i] = r.Next(1, 100); } Array.Sort(arr); } //折半查找算法 返回查找元素的索引位置 public int HalfSearch(int key) { int low = 0;//低點,初始值設置成最低點,即索引0 int high = arr.Length - 1;//高點,初始值設置成最高點,即索引數組最後一個位置 //如果數組元素個數是偶數,比如4個,索引2和3都是中間位置,用以下算法中間位置指向索引3 //如果數組元素個數是奇數,比如3個,索引1是中間位置,用以下算法中間位置指向索引1 int middle = (low + high + 1)/2; int location = -1;//找不到就返回-1 //循環,找不到就一直查找 do { //每次循環,把低點和高點位置的元素打印出來 Console.WriteLine(PrintSectionElements(low, high)); Console.WriteLine(); //如果要查找元素是中間位置的元素,就返回中間位置這個索引 if (key == arr[middle]) { location = middle; } else if (key < arr[middle]) //如果要查找元素小於中間位置元素,把中間位置前面的索引設為高點 { high = middle - 1; } else//如果要查找元素大於中間位置元素,把中間位置後面的索引設為低點 { low = middle + 1; } //如果代碼運行到此處,說明還沒有找到匹配元素,由於以上重新設置瞭低點或高點,所以這裡也要重新設置中間位置 middle = (low + high + 1)/2; } while ((low <= high) && (location == -1)); return location; } //打印2個位置間的數組元素 public string PrintSectionElements(int low, int high) { string temp = ""; //對於2個位置間的元素打印出元素並跟上一個空格位置 for (int i = low; i <= high; i++) { temp += arr[i] + " "; } return temp; } //重寫ToString方法,把數組所有的元素都打印出來 public override string ToString() { return PrintSectionElements(0, arr.Length - 1); } }
以上,折半查找的目的是找到匹配元素在數組中的索引位置,為此,通過需查找元素和中間位置元素大小的比較,不斷地調整低點、高點和中間位置。另外,在C#中,1/2的結果是0。
客戶端。
class Program { private static int key; //需查找元素 private static int position;//匹配元素所在的位置 static void Main(string[] args) { MyArray myArray = new MyArray(7); //把所有元素打印出來 Console.WriteLine(myArray); Console.WriteLine("請輸入需要查找的元素或輸入-1退出 "); key = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); while (key != -1) { //調用折半算法得出所需查找元素的位置 position = myArray.HalfSearch(key); if (position == -1) //說明沒有找到需要匹配的元素 { Console.WriteLine("沒有找到元素{0}", key); } else { Console.WriteLine("在{0}號位置查到元素{1}", position, key); } Console.WriteLine("請輸入需要查找的元素或輸入-1退出 "); key = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); } } }
用時間復雜度來描述折半查找的效率
假設一個數組有1023個元素,由於可以表示成"1023=2ⁿ-1"等式,所有n=10。對該數組每進行一次折半,相當於除以2,也就是說,在該數組中查找某個元素,最多需要10次,就可以查到匹配元素。
對於"2ⁿ-1"這個表達式,當n=30,就表示10億,使用折半查找,10億個元素最多需要30次就能找到匹配元素。而使用線性查找需要平均5億次的查找。2種算法的效率由此可見一斑。
把折半查找、二分查找的時間復雜度寫成O(log n),稱為"對數運行時間",讀為"對數階"。
以上就是這篇文章的全部內容瞭,希望本文的內容對大傢的學習或者工作具有一定的參考學習價值,謝謝大傢對WalkonNet的支持。如果你想瞭解更多相關內容請查看下面相關鏈接