二分查找的两种方法（详细图解）

一、什么是二分查找

假设给定的数组中的元素是一个有序的状态，比如是单调不递减或者是单调不递增的状态，对于这种情况可以使用二分查找来完成。即二分查找需要满足两个条件：

（1）数组存储 （2）元素有序，单调性

二、时间复杂度

比如：总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。 由于n/2^k取整后>=1，即令n/2^k=1， 可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)

三、详细图解

例如；给定一升序数组nums={2,3,4,5,6,7,8,9}，求数字6所在数组中位置；

利用二分查找如图；

解题步骤；

（1）、定义两指针left和right；left指向数组头部，right指向数组尾部；

（2）、求两指针中间值mid=（left+right）/2，获取mid位置的值nums[mid]；

（3）、用nums[mid]与所求值6比；较因mid值小于6；又因数组为升序所以mid左部元素均小于6；

（4）、接下来只需在mid右边查找；所以left指针移至mid+1处；

（5）、重复（1），（2），（3），（4）步骤，如果mid值等于所求值六则返回下标；如果left>right 则表示没有该元素，返回-1；

四、代码实现

由图例及解题思想可知；

例题：给定一升序数组nums={2,3,4,5,6,7,8,9}，求数字6所在数组中位置；

输出结果：4

方法一：while循环判断

public class SearchNum {
    public static void main(String[] args){
        int []nums = {2,3,4,5,6,7,8,9};
        int num = 6;
        System.out.print(searchnum(nums,num));
    }

    public static int searchnum(int[]nums,int num){
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]==num){
               return mid;
            }
            else if(nums[mid]<num){
                left = mid+1;
            }
            else if(nums[mid]>num){
                right = mid-1;
            }

        }
        return -1;
    }
}

方法二：递归

public class SearchNum {
    public static void main(String[] args){
        int []nums = {2,3,4,5,6,7,8,9};
        System.out.print(binarySearch(nums,0,nums.length-1,6));
    }

    private static int binarySearch(int[] arr, int L, int R, int key) {

        if (L > R) {    //元素key不存在
            return -1;
        }
        int M = (L + R) / 2;
        if (arr[M] == key) {
            return M;
        }
        if (arr[M] < key) {
            return binarySearch(arr,M + 1, R, key);
        } else {
            return binarySearch(arr,L, M - 1, key);
        }
    }
}

运行结果：