一、基本概念

二分查找法（Binary Search）算法，也叫折半查找算法。二分查找要求数组数据必须采用顺序存储结构有序排列。查找思想有点类似于分治思想。每次都通过跟区间的中间元素对比，将带查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。二分查找是一种非常非常高效的查询算法，时间复杂度为O(logn)。

二、算法实现

之前有写过利用数组进行数据查找的文章，其采用的是二分查找，不过原先的实现代码并不通用，因为源代码只适用于整型数组，倘若要求在浮点数组或者字符串数组中查找，那只能重新编码了。

因此，对于这种基本逻辑结构雷同、仅有数据类型不同的算法，完全可以采取泛型的手段处理。

接下来就利用泛型实现通用的二分查找算法。

注意： 凡是实现了Comparable接口的数据类型（即包装类型，不是基本数据类型），它的数组都能运用泛型方法进行二分查找。

泛型方法的定义：

	// 二分查找的入口方法。注意泛型类型T必须实现了接口Comparable
	// 请求参数为待查找的数组及目标元素，返回参数为目标元素的数组下标（位置）
	public static <T extends Comparable<T>> int binarySearch(T[] array, T aim);

定义好泛型的规格后，还得在方法体补充详细的代码逻辑，除了要将比较大小的大于号和小于号换成compareTo方法外，整体的查找过程既可沿用原来的for循环语句，又可以采用严谨的递归方式。

【方法一】：递归方式

封装了二分查找泛型方法的工具类

//二分查找算法的工具类。使用了泛型方法
public class ArrayFind {
	private static int count; // 查找次数

	// 二分查找的入口方法。注意泛型类型T必须实现了接口Comparable
	// 请求参数为待查找的数组及目标元素，返回参数为目标元素的数组下标（位置）
	public static <T extends Comparable<T>> int binarySearch(T[] array, T aim) {
		count = 0; // 开始查找前先把查找次数清零
		return binarySearch(array, 0, array.length - 1, aim);//说白了就是对start、end赋值
	}

	// 使用递归实现的二分查找
	private static <T extends Comparable<T>> int binarySearch(T[] array, int begin, int end, T aim) {
		count++; // 查找次数加一
		if (begin >= end && aim.compareTo(array[begin])!=0) { // 起点和终点都重合了还没找到
			return -1; // 返回-1表示没找到
		}
		//int middle = begin + ((end - begin) >> 1);
		int middle = (begin + end) / 2; // 计算中间的位置
		if (aim.compareTo(array[middle]) == 0) { // 找到目标值，返回目标值所处的位置
			System.out.println("查找次数="+count);
			return middle;
		} else if (aim.compareTo(array[middle]) < 0) { // 目标值在前半段，继续查找
			return binarySearch(array, begin, middle - 1, aim);
		} else { // 目标值在后半段，继续查找
			return binarySearch(array, middle + 1, end, aim);
		}
	}
}

对上面代码加以验证；
步骤：先构造填满元素的数组，然后对其排序，最后再调用ArrayFind的binarySearch方法查找。

//演示如何使用二分查找法在某个数组里面找到目标值
public class TestFind {

	public static void main(String[] args) {
		testIntFind(); // 测试整型数组的查找
		testStrFind(); // 测试字符串数组的查找
	}
	
	// 测试整型数组的查找
	private static void testIntFind() {
		Integer item = 0; // 随机数变量
		Integer[] numberArray = new Integer[20]; // 随机数构成的数组
		// 以下生成一个包含随机整数的数组
		loop: for (int i = 0; i < numberArray.length; i++) {
			item = new Random().nextInt(100); // 生成一个小于100的随机整数
			for (int j = 0; j < i; j++) { // 遍历数组进行检查，避免塞入重复数字
				// 数组中已存在该整数，则重做本次循环，以便重新生成随机数
				if (numberArray[j] == item) {
					i--; // 本次循环做了无用功，取消当前的计数
					continue loop; // 直接继续上一级循环
				}
			}
			numberArray[i] = item; // 往数组填入新生成的随机数
		}
		Arrays.sort(numberArray); // 对整数数组排序（默认升序排列）
		System.out.println();
		for (int seq=0; seq<numberArray.length; seq++) { // 打印数组中的所有数字
			System.out.println("序号="+seq+", 数字="+numberArray[seq]);
		}
		
		// 下面通过二分查找法确定目标数字排在第几位
		Integer aim_item = item; // 最后生成的整数
		System.out.println("准备查找的目标数字="+aim_item);
		// 通过泛型的二分查找方法来查找目标数字的位置
		int position = ArrayFind.binarySearch(numberArray, aim_item);
		System.out.println("查找到的位置序号="+position);
	}

	// 测试字符串数组的查找
	private static void testStrFind() {
		String item = ""; // 随机字符串变量
		String[] stringArray = new String[20]; // 随机字符串构成的数组
		// 以下生成一个包含随机字符串的数组
		loop: for (int i = 0; i < stringArray.length; i++) {
			int random = new Random().nextInt(26); // 生成一个小于26的随机整数
			item = "" + (char) (random + 'A'); // 利用随机数获取从"A"到"Z"的随机字符串
			for (int j = 0; j < i; j++) { // 遍历数组进行检查，避免塞入重复字符串
				// 数组中已存在该整数，则重做本次循环，以便重新生成随机字符串
				if (stringArray[j].equals(item)) {
					i--; // 本次循环做了无用功，取消当前的计数
					continue loop; // 直接继续上一级循环
				}
			}
			stringArray[i] = item; // 往数组填入新生成的随机字符串
		}
		Arrays.sort(stringArray); // 对字符串数组排序（默认升序排列）
		System.out.println();
		for (int seq=0; seq<stringArray.length; seq++) { // 打印数组中的所有字符串
			System.out.println("序号="+seq+", 字符串="+stringArray[seq]);
		}
		
		// 下面通过二分查找法确定目标字符串排在第几位
		String aim_item = item; // 最后生成的字符串
		System.out.println("准备查找的目标字符串="+aim_item);
		// 通过泛型的二分查找方法来查找目标字符串的位置
		int position = ArrayFind.binarySearch(stringArray, aim_item);
		System.out.println("查找到的位置序号="+position);
	}

}

【方二】：for循环语句

	
//二分查找算法的工具类。使用了泛型方法
public class ArrayFind {
	private static int count; // 查找次数

	// 二分查找的入口方法。注意泛型类型T必须实现了接口Comparable
	// 请求参数为待查找的数组及目标元素，返回参数为目标元素的数组下标（位置）
	//for循环语句
	public static <T extends Comparable<T>> int binarySearch_1(T[] array, T aim) {

		return binarySearch_1(array, 0, array.length-1, aim);
	}
	
	private static <T extends Comparable <T>> int binarySearch_1(T[] array,int begin,int end, T aim) {
		int count;
		int position = 0;
		
		for(count = 1; begin <= end; count++) {
			int middle = (begin + end) / 2;
			//int middle = begin + ((end - begin) >> 1);
			if(aim.compareTo(array[middle]) < 0) {
				end = middle - 1;	
			}else if(aim.compareTo(array[middle]) > 0) {
				begin = middle + 1;
			}else {
				position = middle;
				break;
			}
		}
		return position;
	}

实际上，middle=(start+end)/2 这种写法是有问题的。因为如果 start 和 end 比较大的话，两者之和就有可能会溢出。改进的方法是将 middle 的计算方式写成 start+(end-start)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 start+((end-start)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。

【补充】：位运算符 之 左右移

1. 左移(<<)
   参加运算的两个数，换算为二进制(0、1)后，进行左移运算，用来将一个数各二进制位全部向左移动若干位。
   
   注意，观察可以发现，左移一位的结果就是原值乘2，左移两位的结果就是原值乘4。
2. 右移(>>)
   参加运算的两个数，换算为二进制(0、1)后，进行右移运算，用来将一个数各二进制位全部向右移动若干位。
   
   注意，观察可以发现，右移一位的结果就是原值除2，右移两位的结果就是原值除4，注意哦，除了以后没有小数位的，都是向下取整。

三、局限性

1. 二分查找法依赖的是顺序表结构，简单点来说就是数组。主要原因是二分查找方法需要按照下标随机访问元素。如果使用其他数据结构，时间复杂度就会提高。
2. 二分查找针对的是有序数据。所以二分查找只能在插入、删除操作不频繁，一次排序多次查找的场景中；
3. 数据量太小不适合二分查找，如果要处理的数据量很小，顺序遍历就够了。不过，如果元素直接的比较操作非常耗时，例如字符串之间的比较，不管数据量大小，都推荐使用二分查找算法。
4. 数据量太大也不适合用二分查找，因为二分查找依赖于顺序存储结构，要求内存空间连续，如果数据量很大的情况下，可能存在空间不够分配的困难。

四、简单举例

1.【详细讲解过程】
已有9个数字，分别为10,20,30,40,50,60,70,80,90。现需查找数字60。

首先，用图解理解原理：



【代码实现】

		int[] nums = {10,20,30,40,50,60,70,80,90};
		
		//要查找的数据
		int num = 60;
		
		//关键的三个变量
		//1. 最小范围下标
		int minIndex = 0;
		//2. 最大范围下标
		int maxIndex = nums.length - 1;
		//3. 中间下标
		int centerIndex = minIndex + ((maxIndex - minIndex) >> 1);
		
		while(true) {
			if(nums[centerIndex] > num) {
				//中间数据较大
				maxIndex = centerIndex - 1;
			}else if(nums[centerIndex] < num) {
				//中间数据较小
				minIndex = centerIndex + 1;
			}else {
				//找到目标数据，数据位置：centerIndex
				break;
			}
			
			if(minIndex > maxIndex) {
				centerIndex = -1;
				break;
			}
			centerIndex = minIndex + ((maxIndex - minIndex) >> 1);
		}
		System.out.println("目标下标位置：" + centerIndex);

运行结果：

目标下标位置：5

下面这幅图是查找不到相应数据的图解：

2.已经有10个数字，分别是6,8,4,5,9,10,18,17,16,20，现需要查找数字20。

public static int binarySearch(int[] arr, int aim) {
		//1.定左右标尺
		int begin = 0;
		int end = arr.length -1;
		
		//2.标尺不相错，一直循环：根据中值（a、算中值，b、和中值对比），调整标尺返回结果
		while(begin <= end) {//擦肩而过，就退出循环
			int middle = begin + ((end - begin) >> 1);
			
			if(aim < arr[middle]) {//往左走
				end = middle - 1;
			}else if(aim > arr[middle]) {//往右走
				begin = middle + 1;
			}else {
				return middle;
			}

		}
		return -1;
	}

public static void main(String[] args) {
		int[] array = {6,8,4,5,9,10,18,17,16,20};
		Arrays.sort(array);
		for(int seq = 0; seq < array.length; seq++) {
			System.out.println("序号：" + seq + ",对应的值：" + array[seq]);
		}
		int aim = 20;
		System.out.println(ArrayFind_1.binarySearch(array,aim));
	}
		

五、总结

• 确定查找的范围

• 计算中间的下标 minIndex + ((maxIndex - minIndex) >> 1)

• 比较中间下标数据，中间下标数据较大，则最大下标等于中间下标-1；
  比较中间下标数据，中间下标数据较小，则最小下标等于中间下标+1；

• 但最小下标 > 最大下标时，说明数据是不存在的。

折半查找/二分查找算法

• 折半/二分查找算法
• 冒泡排序算法
• 插入排序算法
• 选择排序算法
• 快速排序算法
• 希尔排序算法
• 堆排序算法
• 归并排序算法

给出一个list和一个元素，判断出list中是否存在该元素

浅短理解：

折半查找算法是对于有序的序列而言的，每次查找后折半，大概缩短了一半的查找区间，是一种效率较高的查找算法。

要求：

list必须是顺序结构，且按照关键词大小进行有序排列。

思路：

在有序序列中查找元素，每次取序列中间的元素，如果与要查找元素相等，程序结束；
如果查找元素大于中间元素，则取中间元素后面的序列再进行如上的查找；
如果查找元素小于中间元素，则取中间元素前面的序列再进行如上的查找；
直到找到元素相等，查找成功，或者序列为空，查找失败，程序结束。

python版本：Python2.7.5

# _*_ encoding:utf-8 _*_

def binary_search(lists, key, left, right):
	'''
	lists：有序序列/list
	key：要查找的元素
	left：查找的起始位置
	right：查找的结束位置 -方便使用递归
	return：返回查找元素下标
	'''
	# 查找的起始位置大于等于结束位置，查找失败程序结束
	if left >= right:
		return None
	mid = (right - left) // 2 + left		# 折半，中间元素下标

	if lists[mid] > key:
		# 中间元素大于查找元素，则查找前半序列
		return binary_search(lists, key, left, mid - 1)
	elif lists[mid] < key:
		# 中间元素小于查找元素，则查找后半序列
		return binary_search(lists, key, mid + 1, right)
	else:
		# 中间元素等于查找元素，程序结束返回下标
		return mid


if __name__ == '__main__':

	lt = [3,7,10,11,20,33,36,40,88]
	index = binary_search(lt, 33, 0, len(lt))

	print u'元素位置：{}'.format(index) if index else u'没有找到该元素'

运行结果

文章中有不足之处请多多指教，欢迎讨论，共同学习，共同进步

本教程将介绍Java中的二分查找和递归二分查找算法。

package BinarySearch;

import java.util.*;

class BinarySearchIterative {
	public static void main(String args[]) {
		int numArray[] = { 5, 10, 15, 20, 25, 30, 35 };
		System.out.println("The input array: " + Arrays.toString(numArray));
		// key to be searched
		int key = 20;
		System.out.println("\nKey to be searched=" + key);
		// set first to first index
		int first = 0;
		// set last to last elements in array
		int last = numArray.length - 1;
		// calculate mid of the array
		int mid = (first + last) / 2;
		// while first and last do not overlap
		while (first <= last) {
			// if the mid < key, then key to be searched is in the first half of array
			if (numArray[mid] < key) {
				first = mid + 1;
			} else if (numArray[mid] == key) {
				// if key = element at mid, then print the location
				System.out.println("Element is found at index: " + mid);
				break;
			} else {
				// the key is to be searched in the second half of the array
				last = mid - 1;
			}
			mid = (first + last) / 2;
		}
		// if first and last overlap, then key is not present in the array
		if (first > last) {
			System.out.println("Element is not found!");
		}
	}
}

package BinarySearch;

import java.util.*;

class BinarySearchRecursive {
	// recursive method for binary search
	public static int binary_Search(int intArray[], int low, int high, int key) {
		// if array is in order then perform binary search on the array
		if (high >= low) {
			// calculate mid
			int mid = low + (high - low) / 2;
			// if key =intArray[mid] return mid
			if (intArray[mid] == key) {
				return mid;
			}
			// if intArray[mid] > key then key is in left half of array
			if (intArray[mid] > key) {
				return binary_Search(intArray, low, mid - 1, key);// recursively search for key
			} else // key is in right half of the array
			{
				return binary_Search(intArray, mid + 1, high, key);// recursively search for key
			}
		}
		return -1;
	}

	public static void main(String args[]) {
		// define array and key
		int intArray[] = { 1, 11, 21, 31, 41, 51, 61, 71, 81, 91 };
		System.out.println("Input List: " + Arrays.toString(intArray));
		int key = 31;
		System.out.println("\nThe key to be searched:" + key);
		int high = intArray.length - 1;
		// call binary search method
		int result = binary_Search(intArray, 0, high, key);
		// print the result
		if (result == -1)
			System.out.println("\nKey not found in given list!");
		else
			System.out.println("\nKey is found at location: " + result + " in the list");
	}
}

package BinarySearch;

import java.util.Arrays;

class BinarySearchArrays {
	public static void main(String args[]) {
		// define an array
		int intArray[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
		System.out.println("The input Array : " + Arrays.toString(intArray));
		// define the key to be searched
		int key = 50;
		System.out.println("\nThe key to be searched:" + key);
		// call binarySearch method on the given array with key to be searched
		int result = Arrays.binarySearch(intArray, key);
		// print the return result
		if (result < 0)
			System.out.println("\nKey is not found in the array!");
		else
			System.out.println("\nKey is found at index: " + result + " in the array.");
	}
}