查找算法-二分查找法

**二分查找法

基于排序的基础之上
终止条件：一直折半，直到中间的那个元素恰好是被查找的元素

10 11 12 13 14 15 16 17 18 19 20
找出18的下标

第一次：
（0 + 10）/ 2 –> 中间元素的下标：5
拿着中间这个元素和目标要查找的元素进行对比：
中间元素是：arr[5]  15 < 18  18 在目前中间元素元素15的右边

第二次：
开始下标：5 + 1
结束下标：10
（6 + 10）/ 2 –> 8
中间元素：arr[8]  18
找到目标元素

package javaCoreTest;

//查找1

public class ArraySearch01 {

	public static void main(String [] args) {
		int [] arr = {4, 5, 6, 87, 8};
		
		//第一种方法：一个一个挨着找
		//需求：找出87的下标，如果没有返回-1
		for(int i = 0; i < arr.length; i++) {
			if(arr[i] == 87) {
				System.out.println("87元素的下标是：" + i);
				return;
			}
		}
		
		System.out.println("87不存在");
		
		//第二种方法：二分法查找
	}
}

package javaCoreTest;

//查找2

public class ArraySearch02 {

	public static void main(String [] args) {
		int [] arr = {100, 200, 300, 400, 401, 600};
		
		int index = binarySearch(arr, 200);
		System.out.println(index == -1 ? "该元素不存在！" : "该元素下标" + index);
		
	}
	
	public static int binarySearch(int [] arr, int dest) {
		//开始下标
		int begin = 0;
		// 结束下标
		int end = arr.length - 1;
		
		while(begin <= end) {
			//中间元素下标
			int mid = (begin + end) / 2;
			
			if(arr[mid] == dest) {
				return mid;
			}else if(arr[mid] < dest) {
				//目标在“中间”的右边
				//开始元素重新赋值
				begin = mid + 1;
			}else {
				//目标在“中间”的左边
				//修改结束元素的下标
				end = mid - 1;
			}
		}
			
			return -1;
	}
}