折半查找用与有序数组,是非常优秀的,其思想是比较查找值与数组中间元素,若相等,则结束查找,
若查找值大于中间值,则在数组后半部分查找(数组为升序),反之则在数组前半部分查找

其实现如下:

1.         /// <summary>
   
2.         /// 折半查找
   
3.         /// </summary>
   
4.         /// <param name="arr">要查找的数组</param>
   
5.         /// <param name="keyValue">要查找的值</param>
   
6.         /// <returns>值在数组中的下标,若返回值为-1,则数组中没有此值</returns>
   
7.         /// 数组必须有序,且为升序
   
8.         static int BinarySearch(int[] arr, int keyValue)
   
9.         {
   
10.             int low = 0;
    
11.             int high = arr.Length - 1;
    
12.             int mid;
    
13.             while (low <= high)
    
14.             {
    
15.                 mid = (low + high) / 2;
    
16.                 if (keyValue == arr[mid])
    
17.                 {
    
18.                     return mid;
    
19.                 }
    
20.                 else if (keyValue < arr[mid])
    
21.                 {
    
22.                     high = mid - 1;
    
23.                 }
    
24.                 else
    
25.                 {
    
26.                     low = mid + 1;
    
27.                 }
    
28.             }
    
29.             return -1;
    
30.         }

复制代码

和前两种算法(合并排序,快速排序)相比,(前两种都可以归结为分治法)折半查找是很不规范的分治法,也可以说是分治法的一种退化
其他算法请看这里
若有不对之处还请指出

值得学习ing!