/**
* 测试二分法查找
*/
public class Test Binary Search {
public static int binarySearch(int[] arr,int tar){
/*
使用二分法之前需要对数组排序 这里设定数组是由小到大排序
取中间元素arr[mid]和要查找的数tar比较 如果tar更大就在中间元素的右侧区域即比中间元素大的区域再次取中间元素作比较
如果tar更小就在左侧区域再取中间元素比较 区域每次缩小 一半+mid中间元素本身
如果一直比较到区域内只有一个元素的时候 mid中间元素就是这个元素 用 arr[mid]和tar比较还是不相同即数组中不存在tar返回-1
*/
int low = 0;
int high = arr.length-1;
//第一次查询的区域是整个数组 即第0位至length-1位
int mid;
//设定中间元素用于比较tar
while(low<=high){
mid = (high+low)/2;
//mid不是区域的长度/2 mid是中间元素的下标 应该在下标low和下标high中间 high-low是长度 (high+low)/2是取平均
if(arr[mid] == tar)return mid;
if (arr[mid] >tar){
high=mid-1;
}
if(arr[mid]<tar){
low = mid+1;
}
}
return -1;
}
public static void main(String[] args) {
int[] array1 = {5,7,8,1,3,6,4,2,9};
Arrays.sort(array1);
//查找之前先要排序
System.out.println(Arrays.toString(array1));
System.out.println(binarySearch(array1,8));
//先查array1[mid=4]<8 范围变为low5 high8 mid6 [mid]<8 范围变为low7 high8 mid7 [7]=8返回
System.out.println(binarySearch(array1,0));
/*
arr[mid=4]为5>0 arr[mid=1]为2>0 high变为1-1 while(low0<=high0) mid=(low+high)/2=0
arr[0]为1>0 high变为0-1 while(low<=high)false 退出循环返回-1
*/
}
}
