大话数据结构—二分查找（十一）

1.二分查找

public class BinarySearch {

    //  1.非递归方式
    public static int search1(int[] array, int key) {
        int low = 0;
        int high = array.length - 1;
        int mid = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            if (array[mid] == key) {
                return mid;
            } else if (array[mid] < key) {
                low = mid + 1;
            } else if (array[mid] > key) {
                high = mid - 1;
            }
        }
        return -1;
    }

    // 2.递归方式
    public static int search2(int[] array, int low, int high, int key) {
        if (low <= high) {
            int mid = (low + high) / 2;
            if (array[mid] == key) {
                return mid;
            } else if (array[mid] < key) {
                return search2(array, mid + 1, high, key);
            } else if (array[mid] > key) {
                return search2(array, low, mid - 1, key);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 4, 6, 345, 655, 866};
        System.out.println(search1(array, 4));
        System.out.println(search1(array, 655));
        System.out.println(search1(array, 565));
        System.out.println("-----------");
        System.out.println(search2(array, 0, array.length - 1, 6));
        System.out.println(search2(array, 0, array.length - 1, 3));
        System.out.println(search2(array, 0, array.length - 1, 655));
        System.out.println(search2(array, 0, array.length - 1, 346));
    }

}