折半查找

 1 // --------------------------------------------------------------------------------------------------------------------
 2 // <copyright company="Chimomo's Company" file="Program.cs">
 3 // Respect the work.
 4 // </copyright>
 5 // <summary>
 6 // The binary search (not recursive).
 7 // [折半查找的前提]：
 8 // 1、待查找序列必须采用顺序存储结构。
 9 // 2、待查找序列必须是按关键字大小有序排列。
10 // </summary>
11 // --------------------------------------------------------------------------------------------------------------------
12 
13 namespace CSharpLearning
14 {
15     using System;
16 
17     /// <summary>
18     /// The program.
19     /// </summary>
20     internal class Program
21     {
22         /// <summary>
23         /// Entry point into console application.
24         /// </summary>
25         public static void Main()
26         {
27             int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
28             Console.WriteLine(BinarySearch(a, 6, 9));
29         }
30 
31         /// <summary>
32         /// 在长度为n的有序数组a中查找值为key的元素（非递归查找）。
33         /// </summary>
34         /// <param name="a">
35         /// 待查找数组。
36         /// </param>
37         /// <param name="key">
38         /// 目标元素。
39         /// </param>
40         /// <param name="n">
41         /// 数组长度。
42         /// </param>
43         /// <returns>
44         /// 若查找到目标元素则返回该目标元素在数组中的下标；否则返回-1。
45         /// </returns>
46         private static int BinarySearch(int[] a, int key, int n)
47         {
48             int low = 0;
49             int high = n - 1;
50             while (low <= high)
51             {
52                 int mid = (low + high) / 2;
53                 if (a[mid] == key)
54                 {
55                     return mid;
56                 }
57 
58                 if (a[mid] < key)
59                 {
60                     low = mid + 1;
61                 }
62                 else
63                 {
64                     high = mid - 1;
65                 }
66             }
67 
68             return -1;
69         }
70     }
71 }
72 
73 // Output:
74 /*
75 5
76 */