I学霸官方免费教程二十九：Java查找算法之二分法查找

二分法查找算法

基本步骤：
第一步：获取数组中间的下标
第二步：中间下标处的值和目标值比较，如果目标值大，说明要找的值在数组的后边一半中
第三步：再次获取数组右边一半的中间下标
第四步：再次用获得的中间下标和目标值进行比较
后续步骤以此类推，这样每次查找都在“半份”数据中进行，所以又叫折半查找。这也是为什么使用二分法查找之前必须要对数组进行排序的原因。如果不排序，将无法判断目标值在哪“半份”中

实例：
package algorithm.binary_search;
/**
 * 演示二分法查找算法
 * @author 学霸联盟 - 赵灿
 */
public class BinarySeachDemo {
	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
		//目标值，查找6在数组中的下标
		int tagValue = 6;
		int index = binarySeach(arr, tagValue);
		if(index > -1){
			System.out.println("目标值：" + tagValue + "的下标为：" + index);
		} else {
			System.out.println("没有找到目标值：" + tagValue);
		}
	}
	/**
	 * 实现二分法查找的方法
	 */
	public static int binarySeach(int[] arr, int tagValue){
		//查找范围的第一个下标
		int firstIndex = 0;
		//查找范围的最后一个下标
		int lastIndex = arr.length - 1;
		//如果第一个下标比最后一个下标还大，就没有必要再查找了，结束循环
		while (firstIndex <= lastIndex) {
			//获取查找范围中间的下标
			int index = (lastIndex - firstIndex) / 2 + firstIndex;
			if(arr[index] == tagValue){
				//如果两个值相等，说明index就是要找的下标
				//如果找到目标值，执行此处的return语句
				return index;
			} else if(arr[index] > tagValue){
				//如果中间下标处的值比目标值大，说明查找范围在index的左侧
				//所以应该将查找范围的最后一个下标设置为index-1
				lastIndex = index - 1;
			} else {
				//否则说明查找范围在index的右侧
				//所以应该将查找范围的第一个下标设置为index+1
				firstIndex = index + 1;
			}
		}
		//如果循环执行完了还没有找到，返回-1
		//因为数组的下标不可能为-1，所以-1代表没有找到
		return -1;
	}
}
运行结果：
目标值：6的下标为：5

版权声明：本文为博主原创文章，未经博主允许不得转载。