二分查找

定义

二分查找（Binary Search）又称折半查找，它是一种效率较高的查找方法。

要求

（1）必须采用顺序存储结构

（2）必须按关键字大小有序排列

查找思路

首先将给定值K，与表中中间位置元素的关键字比较，若相等，返回该元素的存储位置；若不等，这所需查找的元素只能在中间数据以外的前半部分或后半部分中。然后在缩小的范围中继续进行同样的查找。如此反复直到找到为止。

适用情况

该查找方法仅适合于线性表的顺序存储结构，不适合链式存储结构，且要求元素按关键字有序排列。

优缺点

虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。

非递归实现代（还有一种用递归实现的二分查找）

Java代码如下（自己写的，有兴趣的可以查看Java源码）：

import java.util.Arrays;

public class BinarySearch {

	public static void main(String[] args) {

		// 测试代码

		int[] arr = { 4, 58, 69, 54, 2, 48, 62, 78 };

		// 对数组进行排序，以便使用二分查找（也称折半查找），并打印排序后的数组，

		System.out.println(Arrays.toString(arr));

		System.out.println(myBinarySearch(arr, 69));

	}

	/**

	 * @param arr    操作数组

	 * @param target 查找目标

	 * @return 查找到，返回目标在数组中的索引，没找到返回-1

	 */

	public static int myBinarySearch(int[] arr, int target) {

		int start = 0;// 开始查找的索引

		int end = arr.length - 1;// 结束查找的索引

		while (start <= end) {

			int mid = (start + end) / 2;

			if (target == arr[mid]) {

				return mid;

			}

			if (target > arr[mid]) {

				start = mid + 1;

			}

			if (target < arr[mid]) {

				end = mid - 1;

			}

		}

		// 没找到返回-1

		return -1;

	}// myBinarySearch

}