转载

Java|实现二分法查找

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

前言

不知道大家玩过这么一个游戏没---猜数字大小。先在心里想一个100以内的数字，然后参与者来猜数字，每次只提示大了或者小了，直到参与者猜中心中所想的数为止。

怎么来快速猜出来呢？利用二分法查找就可以快速实现。接下来给大家讲解二分法查找的思想，以及如何用java代码实现。

二分法查找的思想

二分法查找又称为折半查找，二分法查找的基本思想是把数组中的元素从小到大有序地存放进数组中，首先将给定值与数组中间位置的值作比较，如果相等，则匹配成功。否则，若比较值小了，则在数组的前半部分继续二分法查找；若比较值大了，则在数组后半部分进行二分法查找。如此循环往复，直到比较值与中间值匹配，完成查找。

流程图：

Java|实现二分法查找

Java代码实现：

public class test {
public static void main(String[] args) {
//        定义数组
int[] arr ={81,51,88,15,59,20,1,50,66,77,4};
//        对数组进行升序排序
Arrays.sort(arr);
//        打印数组
System.out.println(Arrays.toString(arr));
//        打印查找结果
System.out.println(binarySearch(arr,59));
}
public static int binarySearch(int[]arr,int value){
int low = 0;
int high = arr.length-1;
//        循环直到不能再分
while (low<=high){
int mid = (low+high)/2;
if (value == arr[mid]){
//                返回匹配值的下标
return mid;
}
if (value < arr[mid]){
high = mid-1;
}
if (value > arr[mid]){
low = mid+1;
}

}
//        如果没有查找到值，则返回404
return 404;
}
}