二分查找也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
示例
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;
}
}
请注意以上递归实现为尾递归：尽量使用尾递归
在最坏的情况下，二分查找需要在最后一次才能查找到目标关键字，假设原问题规模为n，每次折半原问题，设在第k次时问题规模变为1，那么令 2^k=1 ，因为指数和对数互为逆运算，解得 k=log_{2}n ，即二分查找在最坏的情况下的时间复杂度为： O(logn) 。
