二分查找

二分查找（binary search），也称折半搜索，是一种在 有序数组 中 查找某一特定元素 的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

• 时间复杂度:折半搜索每次把搜索区域减少一半，时间复杂度为O(log n)。（n代表集合中元素的个数）
• 空间复杂度: O(1)。虽以递归形式定义，但是尾递归，可改写为循环。

public static void main(String[] args) {
        int[] arr = {19, 41, 50, 93, 135, 210, 386};
        erFen(arr, 41);
        System.out.println(Arrays.toString(arr));
    }

    public static void erFen(int[] arr, int t) {

        //首先二分查找是在一个有序数组中进行的
        //每次都是找到数组的没一半来锁定所查找的值
        int left = 0;//定义一个左指针
        int right = arr.length;//定义右指针
        while (left < right) {
            int middle = (left + right) / 2;//中间值在随着左右指针移动而改变这样才能缩小范围
            if (arr[middle] == t) {
                System.out.println("下标为" + middle);
                return;
            }
            //当t 大于middle时，说明t在中间值的右边，然后把做指针指先中间并++，++的作用不至于出现死循环
            if (arr[middle] < t) {
                left = middle;
                left++;
            }
            //当t 小于middle时，说明t在中间值的左边，然后把做指针指先中间并--，--的作用不至于出现死循环
            if (arr[middle] > t) {
                right = middle;
                right--;
            }
        }
        System.out.println("没有找到");
    }

    //使用递归
    //递归同理，区别就是将循环使用到递归中，将左右指针传入到递归中
    public static void erFenSelect1(int[] arr, int t1, int l, int r) {

        int left = l;
        int right = r;
        int middle = (left + right) / 2;
        if (arr[middle] == t1) {
            System.out.println(middle);
            return;
        }
        if (arr[middle] > t1) {
            right = middle;
            right--;
        }
        if (arr[middle] < t1) {
            left = middle;
            left++;
        }
        if (left >= right) {
            System.out.println("没有找到");
            return;
        }
        erFenSelect1(arr, t1, left, right);
    }