Java教程

二分查找整理(左闭右闭写法)

本文主要是介绍二分查找整理(左闭右闭写法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1. 数组中没有重复值

// 非递归方式
public int binarySearch(int[] nums, int target){
    int left = 0, right = target.length -1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(nums[mid] < target){ 
            left = mid + 1;
        } else if(nums[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return left;
}

// 递归方式
public int binarySearch(int[] nums, int target, int left, int right){
    if(left > right){ 
        return left;
    }
    int mid = left + (right - left) / 2;
    if(nums[mid] < target){
        return binarySearch(nums, target, mid+1, right);
    } else if(nums[mid] > target){
        return binarySearch(nums, target, left, mid-1);
    } else {
        return mid;
    }
}

2. 数组中有重复值, 找到第一个出现的地方

// 非递归方式
public int binarySearchFirst(int[] nums, int target){
    int left = 0, right = target.length -1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(nums[mid] < target){ 
            left = mid + 1;
        } else if (nums[mid] >= target) {
            right = mid - 1;
        }
    }
    return left;
}
//递归方式
public int binarySearchFirst(int[] nums, int target, int left, int right){
    if(left > right){
        return left;
    }
    int mid = left + (right - left) >> 1;
    if(nums[mid] < target){
        return binarySearchFirst(nums, target, mid+1, right);
    } else if(nums[mid] >= target){
        return binarySearchFirst(nums, target, left, mid-1);
    }
}

 

这篇关于二分查找整理(左闭右闭写法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!