C#二分查找算法设计实现

1.介绍

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。(记住了前提要求是顺序存储结构，而且要有序排序，所以说对于一个无序的是没法用二分查找的）

2.查找算法过程

举例就一个int类型数组为例 比如int[] intArray；

假设数组中元素是按升序排列，将数组中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

复杂度：O（lg n），n为要查找的元素个数。

3.算法要求

1. 必须采用顺序存储结构。
2. 必须按关键字大小有序排列。

4.算法实现

这里以C#代码实现  

4.1递归方法

1 1         /// <summary>
2 2         /// 二分查找递归实现
3 3         /// </summary>
4 4         /// <param name="arr">数组</param>
5 5         /// <param name="low">开始索引 0</param>
6 6         /// <param name="high">结束索引 </param>
7 7         /// <param name="key">要查找的对象</param>
8 8         /// <returns>返回索引</returns>
9 9         public static int BinarySearch(int[] arr, int low, int high, int key)
1010         {
1111             int mid = (low + high) / 2;//中间索引
1212             if (low > high)
1313                 return -1;
1414             else
1515             {
1616                 if (arr[mid] == key)
1717                     return mid;
1818                 else if (arr[mid] > key)
1919                     return BinarySearch(arr, low, mid - 1, key);
2020                 else
2121                     return BinarySearch(arr, mid + 1, high, key);
2222             }
2323         }

4.2While循环实现

1 1         /// <summary>
2 2         /// 二分查找While循环实现
3 3         /// </summary>
4 4         /// <param name="nums">数组</param>
5 5         /// <param name="low">开始索引</param>
6 6         /// <param name="high">结束索引</param>
7 7         /// <param name="target">要查找的对象</param>
8 8         /// <returns>返回索引</returns>
9 9         public static int BinaryWhile(int[] nums, int low, int high, int target)
1010         {
1111             while (low <= high)
1212             {
1313                 int middle = (low + high) / 2;
1414                 if (target == nums[middle])
1515                 {
1616                     return middle;
1717                 }
1818                 else if (target > nums[middle])
1919                 {
2020                     low = middle + 1;
2121                 }
2222                 else if (target < nums[middle])
2323                 {
2424                     high = middle - 1;
2525                 }
2626             }
2727             return -1;
2828         }

5.测试代码

1 1         static void Main(string[] args)
2 2         {
3 3             int[] intArray = new int[] { 1,2,3,4,5,6,7,8,9,10};
4 4             int result = BinarySearch(intArray,0,intArray.Length-1,5);
5 5             Console.WriteLine(result.ToString());
6 6             Console.WriteLine("-------------------------------------------");
7 7             int resuleWhile = BinaryWhile(intArray,0,intArray.Length-1,5);
8 8             Console.WriteLine(resuleWhile.ToString());
9 9             Console.Read();
1010         }

6.输出结果

7.源代码工程下载

源码工程项目文件下载