二分查找基础知识

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        // 待搜索数组 a
        int[] a = {1,2,3,4,5,6,7,8,9};

        // 目标值 1
        int key1 = 3;

        int result1 = binarySearch(a,0,a.length - 1,key1);

        System.out.println("result1 : " + result1);

        // 目标值 2
        int key2 = 88;

        int result2 = binarySearch(a,0,a.length - 1,key2);

        System.out.println("result2 : " + result2);




        return 0 ;

    }


    // 函数传入待搜索数组 a ,搜索当前区间的左端点 left 和当前区间的右端点 right
    // 目标值是 key
    // 如果目标值 key 在数组 a 中,那么返回 key 所在的下标
    // 如果目标值 key 不在数组 a 中,那么返回 -1
    private int binarySearch(int[] a ,int left,int right ,int key){

        // 如果 left 大于 right,说明区间不合法
        if(left > right){
            // 代表没有找到目标值,返回 -1
            return -1;
        }

        // 计算当前区间的中间位置
        // 为了避免出现数据溢出的情况,不使用 (left + right) / 2
        // 而是使用 left  + ( right - left ) / 2;
        int mid = left  + ( right - left ) / 2;

        // 当 key 等于 a[mid] ,说明找到了目标值
        if( key == a[mid]){
            // 返回下标 mid
            return mid;

        // 如果 key 小于 a[mid]
        }else if( key < a[mid]){
            // 需要在左侧区间搜索
            return binarySearch( a , left , mid - 1 ,key);

        // 如果 key 大于于 a[mid] 
        }else if(key > a[mid]){
            // 需要在右侧区间搜索
            return binarySearch( a , mid + 1 , right ,key);
        }

        return - 1;

    }

}

发表评论

邮箱地址不会被公开。 必填项已用*标注