leetcode 704. 二分查找JAVA

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

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);
        }
    }
}