[C#] 二位元搜尋法 (Binary Search)

2010-04-12

11014
0

Introduction

欲搜尋的對象必須已先由小到大的順序排列，搜尋時檢視中間的元素是否與關鍵值相等，如果相等就完成搜尋。

如果關鍵值的值比較大，表示要找的元素在左半邊，在左半邊繼續做二位元搜尋。否則在右半邊繼續做搜尋。

Examples

   private static int binarySearch(int[] list, int item) {
            int left = 0, right = list.Length; //設定左右邊界

            while (left <= right) {
                int mid = (left + right) / 2; 	// 取中間點位置索引
                if (list[mid] == item) {
                    return mid;
                }
                if (list[mid] < item) { 		// 元素大於中間值，在右半繼續做二元搜尋
                    left = mid + 1;             // 調整左邊位置索引
                } else {                        // 元素小於中間值 ， 在左半繼續做二元搜尋
                    right = mid - 1;		    // 調整右邊位置索引
                }
            }	
            return -1;
        }
        static void Main(string[] args) {
            int[] list = new int[8] { -8,-7,-5,1,12,27,35,56 };//由小到大排序好
            Console.WriteLine("輸入欲搜尋的元素");
            int item = Convert.ToInt32(Console.ReadLine());
            int p = binarySearch(list, item);
            if (p >= 0) {
                Console.WriteLine("元素位置 : " + p);
            } else {
                Console.WriteLine("元素不存在");
            }
            Console.ReadKey();
        }

Refrence

http://en.wikipedia.org/wiki/Binary_search

三小俠小弟獻醜，歡迎指教

回首頁