Java实现二分查找（递归与非递归）

二分查找又叫折半查找，针对的是有序表（升序或者降序的数组）
输入一个值进行查找，在查找过程中，首先与序列中间的元素进行比较,如果大于这个元素,就在当前序列的后半部分继续查找,如果小于这个元素,就在当前序列的前半部分继续查找,直到找到相同的元素,或者所查找的序列范围为空为止。

实现原理：
(1)首先确定整个查找区间的中间位置middle=(left+right)/2;
(2)用待查关键字值与中间位置关键字值进行比较；
若相等，则查找成功；
若大于，则在后半个区域中继续进行折半查找。
若小于，则在前半个区域中继续进行折半查找。
查找成功，返回关键字所在数组下标，没找到返回-1；
算法要求
1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。
3.时间复杂度：O(log2n)

代码实现：

二分查找递归实现

public class binarySearch {//二分查找 递归
    private static int binarySearch(int[] arr, int left, int right, int val) {
        if (val < arr[left] || val > arr[right] || left > right) {
            return -1;
        }
        int middle = (left + right) / 2;
        if (val < arr[middle]) {
            return binarySearch(arr, 0, middle - 1, val);
        }
        if (val > arr[middle]) {
            return binarySearch(arr, middle + 1, right, val);
        } else {
            return middle;
        }
    }

二分查找非递归

private static int search(int[] arr, int val) {//二分查找 非递归
        int left = 0;
        int right = arr.length - 1;
        int middle = 0;
        if (val < arr[left] || val > arr[right] || left > right) {
            return -1;
        }
        while (left <= right) {
            middle = (left + right) / 2;
            if (val < arr[middle]) {
                right = middle - 1;
            } else if (val > arr[middle]) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

测试代码

public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 7, 8, 11, 15, 18, 22};
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入需要查找的数字： ");
        int val = scanner.nextByte();
        //int index = search (arr, val);
        int index = binarySearch(arr, 0, arr.length - 1, val);
        if (index == -1) {
            System.out.println("查找的是 " + val + " 序列中没有该数！");
        } else {
            System.out.println("查找的是 " + val + " 元素下标为 " + index);
        }
    }