二分查找（折半查找）

二分查找

二分查找必要条件有两个

1. 必须是顺序存储结构
2. 必须有序

算法思想

1. 将给定的目标值target与中间位置值作比较，相等则查找成功
2. 若是不相等则利用中间位置记录将表分为前后两个子表。如果target比中间位置值小，则下一次在前一子表继续查找；若target比中间位置值大，则下一次在后一子表继续查找。
3. 重复上面两个操作，不断将查找区间进行对折，知道查找成功;或者查找区间为空，则查找失败。

代码如下

public class BinarySearch {
    public static void main(String[] args) throws Exception {
        int[] array = generateArray();
        int target = 12;
        printArray(array);
        int result = binarySearch(array, target);
        System.out.println(result == -1 ? "未查找到目标数据 : " + target : "查找到目标数据，在第" + result + "号元素");
    }

    private static int[] generateArray() {
        int length = 10 + new Random().nextInt(20);
        int[] array = new int[length];
        for (int i = 0; i < array.length; i++) {
            array[i] = 2 + 2 * i;
        }
        return array;
    }

    private static void printArray(int[] array) {
        System.out.println("数组内容是：");
        for (int i : array) {
            System.out.print(i + "\t");
        }
        System.out.print("\n");
    }
    
    //二分查找代码部分
    public static int binarySearch(int[] array, int target) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (target == array[mid]) {
                return mid;
            } else if (target < array[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
}