使用java进行二分查找

使用java进行二分查找

前言：如有错误，欢迎指教

原始二分查找

原始二分查找就是在一个有序数组中查询是否存在元素target，如果存在返回其下标，不存在则返回-1；

public static int binarySearch(int[] nums, int target){

        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            
            //int mid = (left + right) / 2;
            int mid = left + (right - left) / 2;

            //如果与相等直接返回mid
            if(nums[mid] == target){
                return mid;
            }
            //如果target小，我们就往左边搜索
            else if(target < nums[mid]){
                right = mid - 1;
            }
            //如果target大，我们就往右边搜索
            else if(target > nums[mid]){
                left = mid + 1;
            }
        }
        //说明没有找到
        return -1;
    }

值得注意的是，如果你使用以下：

int mid = (left + right) / 2;

可能会出现整型溢出，即right + left的值超过了整型的最大值，因此我们最好使用 left + (right - left) / 2;

二分查找求左边界

    //比target小的元素的个数
    public static int left_bound(int nums[], int target){
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            //在右边
            if(target > nums[mid]){
                left = mid + 1;
            }
            //在左边
            else if(target < nums[mid]){
                right = mid - 1;
            }
            //检查左边还有和target相等的数
            else if(target == nums[mid]){
                right = mid - 1;
            }
        }
        //返回的是个数
        return left;
    }

二分查找求右边界

    //返回比target大的元素的个数，没有的话返回0
    public static int right_bound(int nums[], int target){

        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = left + (right - left)/2;

            if(target > nums[mid]){
                left = mid + 1;
            }
            else if(target < nums[mid]){
                right = mid - 1;
            }
            else if(target == nums[mid]){

                left = mid + 1;
            }
        }
        return nums.length - right - 1;
    }