再看二分查找



  • 最基本的二分查找

    int binarySearch(int[] nums, int target) {
        int left = 0; 
        int right = nums.length - 1; // 注意
    
        while(left <= right) {
            int mid = left + (right - left) / 2; //注意
            if(nums[mid] == target)
                return mid; 
            else if (nums[mid] < target)
                left = mid + 1; 
            else if (nums[mid] > target)
                right = mid - 1; 
        }
        return -1;
    }
    

    寻找左侧边界的二分查找——查找有多少个数小于目标数

    int leftBound(int[] nums,int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid-1;
                }
            }
            if(left>=nums.length || nums[left+1]!=target){
                return -1;
            }
            return left;
        }
    

    寻找右侧边界的二分查找

    int rightBound(int[] nums, int target) {
            int left = 0;
            int right = nums.length-1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] > target) {
                    right = mid-1;
                } else {
                    left = mid+1;
                }
            }
            if(right<0 || nums[right]!=target){
                return -1;
            }
            return nums.length-1-right;
        }
    




  • 太棒了,向你学习


登录后回复
 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

与 Dian 的连接断开,我们正在尝试重连,请耐心等待