数组二分查找-Java 实现

二分查找法作为一种常见的查找方法，大大缩短了搜索时间，时间复杂度只有O(logn)，但它必须在有序数据中进行查找。

二分查找很好写，却很难写对，出错原因主要集中在判定条件和边界值的选择上，很容易就会导致越界或者死循环的情况。

下面给出 Java 的实现代码：

import java.util.Arrays;
import java.util.Scanner;

public class Test01 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = in.nextInt();
        }
        System.out.println("数组输入完毕");
        // 二分查找先排序，Arrays.sort() 默认升序
        Arrays.sort(num);
        binarySearch(num);
        
        in.close();
    }

    public static void binarySearch(int[] num) {
        Scanner in = new Scanner(System.in);
		// 输入要查找的数
        while (in.hasNext()) {
            boolean flag = false;
            int x = in.nextInt();
            int left = 0, right = num.length-1;
            while (left <= right) {
                int mid = (left + right)/2;
                if (num[mid] == x) {
                    System.out.println("查到了：" + x + " 在" + mid);
                    flag = true;
                    break;
                }
                if (num[mid] > x) {
                    right = mid-1;
                }
                else {
                    left = mid+1;
                }
            }
            if (!flag) {
                System.out.println("没查到，不存在");
            }
        }

        in.close();
    }
}