java中实现二分法查找

二分查找只能查找已经排好序的数组，它通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是右边，每一次查找都可以将查找范围减半。查找范围内只剩下一个数据时，查找结束。数据量为n的数组，它的时间复杂度为O(logn)。
具体例子如下：

import java.util.Scanner;
public class ArrayUtil {
    public static void main(String[] args) {
        int[] arr = {100, 200, 230, 234, 235, 245, 565, 768, 3452, 5889, 9999};
        Scanner sc = new Scanner(System.in);
        int a;
        while (true) {
            a = sc.nextInt();
            //找出这个数组中234所在的下标
            //调用方法
            int index = binarySearch(arr, a);
            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;
    }
}

运行结果：

其实java工具类中也提供了二分法查找的方法，只需要调用即可，在Arrays类中，也是binarySearch方法。