二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。 

Bentley在他的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。

折半查找法的优点是比较次数少，查找速度快，平均性能好; 其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

算法步骤描述
① 首先确定整个查找区间的中间位置 mid = （ left + right ）/ 2
② 用待查关键字值与中间位置的关键字值进行比较；
　 若相等，则查找成功
　 若大于，则在后（右）半个区域继续进行折半查找
　 若小于，则在前（左）半个区域继续进行折半查找
③ 对确定的缩小区域再按折半公式，重复上述步骤。
最后，得到结果：要么查找成功， 要么查找失败。折半查找的存储结构采用一维数组存放。
折半查找算法举例
对给定数列（有序）{ 3,5,11,17,21,23,28,30,32,50,64,78,81,95,101}，按折半查找算法，查找关键字值为81的数据元素。
折半查找的算法讨论：
优点：ASL≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。
缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。
考虑：能否通过一次比较抛弃更多的部分（即经过一次比较，使查找范围缩得更小），以达到提高效率的目的。……？
可以考虑把两种方法（顺序查找和折半查找）结合起来，即取顺序查找简单和折半查找高效之所长，来达到提高效率的目的？实际上这就是分块查找的算法思想。
Java二分查找源码  

package com.thread.wait.test;

public class BinarySearch { 
	
	/**
	 * 二分查找算法 : 在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回-1 　　
	 * 
	 * @param srcArray
	 *            有序数组
	 * @param key
	 *            查找元素
	 * @return key的数组下标，没找到返回-1
	 * */
	public static void main(String[] args) {
		int srcArray[] = { 3, 5, 11, 17, 21, 23, 28, 30, 32, 50, 64, 78, 81,
				95, 101 };
		System.out.println(binSearch(srcArray, 0, srcArray.length - 1, 81));
	}

	/**
	 * 二分查找递归实现
	 * 
	 * @param srcArray
	 * @param start
	 * @param end
	 * @param key
	 * @return
	 */
	public static int binSearch(int srcArray[], int start, int end, int key) {
		int mid = (end - start) / 2 + start;
		if (srcArray[mid] == key) {
			return mid;
		}
		if (start >= end) {
			return -1;
		} else if (key > srcArray[mid]) {
			return binSearch(srcArray, mid + 1, end, key);
		} else if (key < srcArray[mid]) {
			return binSearch(srcArray, start, mid - 1, key);
		}
		return -1;
	}

	/**
	 * 二分查找普通循环实现
	 * 
	 * @param srcArray
	 * @param key
	 * @return
	 */
	public static int binSearch(int srcArray[], int key) {
		int mid = srcArray.length / 2;
		if (key == srcArray[mid]) {
			return mid;
		}
		int start = 0;
		int end = srcArray.length - 1;
		while (start <= end) {
			// 使用 (low + high) / 2 会有整数溢出的问题
			mid = (end - start) / 2 + start;
			if (key < srcArray[mid]) {
				// 继续在R[low..mid-1]中查找
				end = mid - 1;
			} else if (key > srcArray[mid]) {
				// 继续在R[mid+1..high]中查找
				start = mid + 1;
			} else {
				return mid;
			}
		}

		// 当low>high时表示查找区间为空，查找失败
		return -1;
	}
 

}

补充：

在学习算法的过程中，我们除了要了解某个算法的基本原理、实现方式，更重要的一个环节是利用big-O理论来分析算法的复杂度。在时间复杂度和空间复杂度之间，我们又会更注重时间复杂度。
时间复杂度按优劣排差不多集中在：
O(1), O(log n), O(n), O(n log n), O(n2), O(nk), O(2n)
到目前位置，似乎我学到的算法中，时间复杂度是O(log n),好像就数二分查找法，其他的诸如排序算法都是 O(n log n)或者O(n2)。但是也正是因为有二分的 O(log n), 才让很多 O(n2)缩减到只要O(n log n)。
 
关于二分查找法
二分查找法主要是解决在“一堆数中找出指定的数”这类问题。
而想要应用二分查找法，这“一堆数”必须有一下特征：
 
存储在数组中
有序排列
所以如果是用链表存储的，就无法在其上应用二分查找法了。（曽在面试被问二分查找法可以什么数据结构上使用：数组？链表？）
至于是顺序递增排列还是递减排列，数组中是否存在相同的元素都不要紧。不过一般情况，我们还是希望并假设数组是递增排列，数组中的元素互不相同。
二分查找法在算法家族大类中属于“分治法”，分治法基本都可以用递归来实现的。

扩展阅读：
用二分查找法找寻边界值
之前的都是在数组中找到一个数要与目标相等，如果不存在则返回-1。我们也可以用二分查找法找寻边界值，也就是说在有序数组中找到“正好大于（小于）目标数”的那个数。
用数学的表述方式就是：
     在集合中找到一个大于（小于）目标数t的数x，使得集合中的任意数要么大于（小于）等于x，要么小于（大于）等于t。
 
举例来说：
给予数组和目标数
 

  
int array = {2, 3, 5, 7, 11, 13, 17};
int target = 7;
 
那么上界值应该是11，因为它“刚刚好”大于7；下届值则是5，因为它“刚刚好”小于7。
用二分查找法找寻上届
 

  

   
  
  
//Find the fisrt element, whose value is larger than target, in a sorted array 
int BSearchUpperBound(int array[], int low, int high, int target)
{
    //Array is empty or target is larger than any every element in array 
    if(low > high || target >= array[high]) return -1;
    
    int mid = (low + high) / 2;
    while (high > low)
    {
        if (array[mid] > target)
            high = mid;
        else
            low = mid + 1;
        
        mid = (low + high) / 2;
    }

    return mid;
}
  

   
  
 
与精确查找不同之处在于，精确查找分成三类：大于，小于，等于（目标数）。而界限查找则分成了两类：大于和不大于。
如果当前找到的数大于目标数时，它可能就是我们要找的数，所以需要保留这个索引，也因此if (array[mid] > target)时 high=mid; 而没有减1。
用二分查找法找寻下届
 

  

   
  
  
//Find the last element, whose value is less than target, in a sorted array 
int BSearchLowerBound(int array[], int low, int high, int target)
{
    //Array is empty or target is less than any every element in array
    if(high < low  || target <= array[low]) return -1;
    
    int mid = (low + high + 1) / 2; //make mid lean to large side
    while (low < high)
    {
        if (array[mid] < target)
            low = mid;
        else
            high = mid - 1;
        
        mid = (low + high + 1) / 2;
    }

    return mid;
}
  

   
  
 
下届寻找基本与上届相同，需要注意的是在取中间索引时，使用了向上取整。若同之前一样使用向下取整，那么当low == high-1，而array[low] 又小于 target时就会形成死循环。因为low无法往上爬超过high。
 
这两个实现都是找严格界限，也就是要大于或者小于。如果要找松散界限，也就是找到大于等于或者小于等于的值（即包含自身），只要对代码稍作修改就好了：
去掉判断数组边界的等号：
 

  
target >= array[high]改为 target > array[high]
 
在与中间值的比较中加上等号：
 

  
array[mid] > target改为array[mid] >= target
 
 
用二分查找法找寻区域
之前我们使用二分查找法时，都是基于数组中的元素各不相同。假如存在重复数据，而数组依然有序，那么我们还是可以用二分查找法判别目标数是否存在。不过，返回的index就只能是随机的重复数据中的某一个。
此时，我们会希望知道有多少个目标数存在。或者说我们希望数组的区域。
结合前面的界限查找，我们只要找到目标数的严格上届和严格下届，那么界限之间（不包括界限）的数据就是目标数的区域了。
 
 

  

   
  
  
//return type: pair<int, int>
//the fisrt value indicate the begining of range,
//the second value indicate the end of range.
//If target is not find, (-1,-1) will be returned
pair<int, int> SearchRange(int A[], int n, int target) 
{
    pair<int, int> r(-1, -1);
    if (n <= 0) return r;
    
    int lower = BSearchLowerBound(A, 0, n-1, target);
    lower = lower + 1; //move to next element
    
    if(A[lower] == target)
        r.first = lower;
    else //target is not in the array
        return r;
    
    int upper = BSearchUpperBound(A, 0, n-1, target);
    upper = upper < 0? (n-1):(upper - 1); //move to previous element
    
    //since in previous search we had check whether the target is
    //in the array or not, we do not need to check it here again
    r.second = upper;
    
    return r;
}
  

   
  
 
它的时间复杂度是两次二分查找所用时间的和，也就是O(log n) + O(log n)，最后还是O(log n)。
 
在轮转后的有序数组上应用二分查找法
之前我们说过二分法是要应用在有序的数组上，如果是无序的，那么比较和二分就没有意义了。
不过还有一种特殊的数组上也同样可以应用，那就是“轮转后的有序数组（Rotated Sorted Array）”。它是有序数组，取期中某一个数为轴，将其之前的所有数都轮转到数组的末尾所得。比如{7, 11, 13, 17, 2, 3, 5}就是一个轮转后的有序数组。非严格意义上讲，有序数组也属于轮转后的有序数组——我们取首元素作为轴进行轮转。
下边就是二分查找法在轮转后的有序数组上的实现（假设数组中不存在相同的元素）
 
 

  

   
  
  
int SearchInRotatedSortedArray(int array[], int low, int high, int target) 
{
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if (target < array[mid])
            if (array[mid] < array[high])//the higher part is sorted
                high = mid - 1; //the target would only be in lower part
            else //the lower part is sorted
                if(target < array[low])//the target is less than all elements in low part
                    low = mid + 1;
                else
                    high = mid - 1;

        else if(array[mid] < target)
            if (array[low] < array[mid])// the lower part is sorted
                low = mid + 1; //the target would only be in higher part
            else //the higher part is sorted
               if (array[high] < target)//the target is larger than all elements in higher part
                    high = mid - 1;
                else
                    low = mid + 1;
        else //if(array[mid] == target)
            return mid;
    }

    return -1;
}
  

   
  
 
对比普通的二分查找法，为了确定目标数会落在二分后的那个部分，我们需要更多的判定条件。但是我们还是实现了O(log n)的目标。
 
二分查找法的缺陷
二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上：
必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。
数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。
 
解决这些缺陷问题更好的方法应该是使用二叉查找树了，最好自然是自平衡二叉查找树了，自能高效的（O(n log n)）构建有序元素集合，又能如同二分查找法一样快速（O(log n)）的搜寻目标数。

下面这篇是对上面内容的更深入的扩展：

http://www.cnblogs.com/ider/archive/2012/09/08/binary_search_advanced.html

参考：

1.<<编程珠玑>>
2.wiki上关于二分查找的说明:http://en.wikipedia.org/wiki/Binary_search

3.http://www.jzsyz.jzedu.cn/xxjs/Suanfa/commonalg/search/sc02.htm