代码随想录-数组

数组是一个非常基础的数据类型。

数组是存放在连续内存空间上的相同类型数据的集合。
下标从零开始，且元素从只能被覆盖不能被删除。

题单

• 704. 二分查找

704. 二分查找

题目：给定一个排好序的一维数组和一个查找目标，需要给出目标在数组中的下标，若无则返回-1。

递归-我的解

我通过递归完成了这一题。但观察官方是通过循环完成的。循环可以减少方法栈的开销，比递归更好。

class Solution {
    public int search(int[] nums, int target) {
        return searchWithIndex(nums, target, 0, nums.length - 1);
    }
    public int searchWithIndex(int[] nums, int target, int left, int right){
        if(left > right){
            return -1;
        }
        int middle = (int) (left + right) / 2;
        if( nums[middle] == target ){
            return middle;
        }else if( nums[middle] > target ){
            return searchWithIndex(nums, target, left, middle - 1);
        }else{
            return searchWithIndex(nums, target, left + 1, right);
        }
    }
}

循环

所以我通过循环实现一次。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right ){
            int middle =  (left + right) / 2;
            if( nums[middle] > target ){
                right = middle - 1;
            }else if( nums[middle] < target ){
                left = middle + 1;
            }else{
                return middle;
            }
        }
        return -1;
    }
}

结果对比

 结果显示循环确实更快，但是内存并没有更低。我觉得递归方法栈的开销应该比循环体的开销大啊。【挖坑待填】