二分查找

二分查找是一种快速查找数据的算法，也叫折半查找，每次查询后数据的返回都会缩小一半，加快搜索的速度。二分查找的前提是数据必须是有序的，否则无法查找。

主要构思

• 定义一个最大下标，最小下标，和中间下标；
• 用while循环去循环，while 的条件为：中间下标所对应的数不等于当前查找的数；（如果不满足就返回当前定义的初始化的下标）；
• while里加入if条件判断：最大下标要大于等于最小下标；避免查询不到元素；
• 当while循环时，如果当前的数小于当前中间下标对应的数时，下一次循环的数组最大下标就等于max=mid-1 , 例如（ 1 - 100 中查找10；10 小于 50，所以数组下次的最大下标就是 50 - 1 了，下次循环的最小下标是 0，最大下标是 49，达到每次都对折一半查找范围）； 如果当前的数大于中间下标所对应的数时，下一次循环的数组最小下标就是 min = mid + 1 , 例如（1-100 中查找60；10 大于 50；所以数组下次开始的最小下标是 50 + 1；最大下标还是 数组长度-1）；
• 每次实现对半查找都会得到一个新的中间下标；直到循环得到的中间下标对应的数等于所查找的数；

示例代码

package com.etime6;

import java.util.Arrays;

public class Test01 {

	public static void main(String[] args) {
		/**
		 * //二分查找
		 * 二分查找是一种快速检索数据的算法。折半查找。
		 * 每查找一遍范围都会缩小一半，大大提高了检索的速度。
		 */
		int [] arr= {9,5,2,7,11,3,6};
		//二分查找的前提是数组中的元素必须是有序的，否则无法查找
		Arrays.sort(arr);//先对数组就行排序操作
		//2, 3, 5, 6, 7, 9, 11  排序后的元素
		int index = getFind(arr, 7);
		System.out.println(index);//运行结果  4
		
		System.out.println("----------------");
		int index2 = getFind(arr, 12);
		System.out.println(index2);//运行结果  元素 12 不存在  -1

	}
	
	//定义函数方法，传入要查找的数组和数
	public static int getFind(int[] arr,int a) {
		int max=arr.length-1;//第一次查找时的最大下标
		int min=0;//第一查找时的最小下标
		int mid=(max+min)/2;//中间数，用中间去找到值
		
		while (arr[mid]!=a) {//当中间的下标所对应的值不等于它本身时才继续循环，否则返回mid
			if(max>=min) {//最大下标要大于或等于最小下标，防止元素不存在时发生的错误
				//当查找的值小于中间下标对应的数时，就证明查找的数在中间下标所对应的数之前，所以下次循环的初始最大下标等于mid-1;
				if(arr[mid]>a) {
					max=mid-1;
				}
				//当查找的值大于中间下标对应的数时，就证明查找的数在中间下标所对应的数之后，所以下次循环的初始最小下标等于mid+1;
				if(arr[mid]<a) {
					min=mid+1;
				}
				mid=(max+min)/2;//每次循环都得到一个新的中间的下标
			}else {
				System.out.println("元素 "+a+" 不存在");
				mid=-1;//当没查到元素时返回-1，并结束循环
				break;//结束循环，避免无限执行循环
			}
		}
		
		return mid;//循环结束后返回查找的元素所对应的下标
	}
}

原文链接:https://blog.csdn.net/qq_43711597/article/details/114703325