
二分查找(Binary Search)
二分查找也称折半查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
示例
public class Program { public static void Main(string[] args) { int[] array = { 8, 11, 21, 28, 32, 43, 48, 56, 69, 72, 80, 94 }; Console.WriteLine(BinarySearch(array, 80)); Console.WriteLine(BinarySearch(array, 66, 0, array.Length - 1)); Console.ReadKey(); } private static int BinarySearch(int[] array, int key) { //直接求解 var min = 0; var max = array.Length - 1; var mid = 0; while (min <= max) { mid = (min + max) >> 1; if (array[mid] > key) { max = mid - 1; } else if (array[mid] < key) { min = mid + 1; } else if (array[mid] == key) { return mid; } } return -1; } private static int BinarySearch(int[] array, int key, int low, int high) { //递归法 if (low > high) return -1; var mid = (low + high) >> 1; if (array[mid] > key) return BinarySearch(array, key, low, mid - 1); else if (array[mid] < key) return BinarySearch(array, key, mid + 1, high); else return mid; } }
请注意以上递归实现为尾递归,详情参考我的另一篇博文:
C#开发笔记之06-为什么要尽可能的使用尾递归,编译器会为它做优化吗?
以上是二分查找算法的2种实现,以下是这个案例的输出结果:
10 -1
分析
在最坏的情况下,二分查找需要在最后一次才能查找到目标关键字,假设原问题规模为n,每次折半原问题,设在第k次时问题规模变为1,那么令 ,因为指数和对数互为逆运算,解得
,即二分查找在最坏的情况下的时间复杂度为:
。
AlgorithmMan

AlgorithmMan by Iori,AlgorithmMan是使用C#开发的一套用于算法演示的工具。
下载链接:AlgorithmMan-BinaryTreeSort
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/699。