Java教程

leetcode 704. 二分查找JAVA

本文主要是介绍leetcode 704. 二分查找JAVA,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二分查找有两种实现方式,迭代和递归,其时间复杂度为\log N.主要思想是将目标值与数组的中间值做对比,若小于中间值,则在数组的前半段找,否则在后半段找。

1、迭代法不会增加多余的内存空间,java代码如下:

class Solution {
    public int search(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 //防止数字溢出
            if(nums[mid] == target){
                return mid; 
            }else if (nums[mid]>target){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return -1 ;
    }
}

2、递归较为简单,但是要考虑返回值问题,终止条件,出现栈内存溢出的情况,JAVA代码如下:

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums,target,0,nums.length-1);
    }
    public int binarySearch(int[] nums, int target,int left, int right) {
        if(left > right){
            return -1;
        }
        int mid = (left+right)/2;
        if(nums[mid] == target){
            return mid; 
        }else if (nums[mid]>target){
            return binarySearch(nums,target,left,mid-1);
        }else{
            return binarySearch(nums,target,mid+1,right);
        }
    }
}
这篇关于leetcode 704. 二分查找JAVA的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!