二分查找

丑陋并且错误的第一次写的代码

var search = function(nums, target) {
    //思路：target和数组中间的数进行比较，比他大，就把中间数的下一位和数组的最后一位形成一个新数组
    //比他小，就把这个数和第一个数为和为一个新数组。在递归调用nums和target
    //细节：数组元素个数为偶数时，中间值取哪个？现在忘了，就先取下标为数组长度/2的整数吧
    //二分查找的出口？
    if(nums.length%2==0){
        //如果数组长度为偶数
        let midIndex=nums.length/2
        if(nums[midIndex]==target){
            return midIndex
        }
        else if(nums[midIndex]!=target&&nums.length==1){
            return -1
        }
        else{
           if(target>nums[midIndex]){
            nums=nums.slice(midIndex)
            return search(nums,target)
        }
        else{
            nums=nums.slice(0,midIndex)
            return search(nums,target)
        }
        }
 
    }
 
    else{
        //如果数组长度为奇数
        let midIndex=Math.floor(nums.length/2)
        if(nums[midIndex]==target){
            return midIndex
        }
 
        else if(nums[midIndex]!=target&&nums.length==1){
            return -1
        }
        else{
            if(target>nums[midIndex]){
            nums=nums.slice(midIndex)
            return search(nums,target)
        }
        else{
            nums=nums.slice(0,midIndex)
            ret search(nums,target)
        }
        }
    }
};

AI+自己的修改后的代码

 
var search = function(nums, target) {
    if(nums.length===0) return -1;//递归出口
    let midIndex=Math.floor(nums.length/2);
    let midValue=nums[midIndex];
    if(midValue==target) return midIndex//递归出口
    if(target>midValue){
        let result= search(nums.slice(midIndex+1),target);//注意这里可加可不加1，但midValue的值肯定不是target，所以把他给取出了
        return result !==-1? midIndex+result+1:-1//递归出口
    }
    else{
        let result= search(nums.slice(0,midIndex),target);
        return result !==-1? result:-1//递归出口
    }
};

官方题解

二分查找的做法是，定义查找的范围 [left,right]，初始查找范围是整个数组。每次取查找范围的中点 mid，比较 nums[mid] 和 target 的大小，如果相等则 mid 即为要寻找的下标，如果不相等则根据 nums[mid] 和 target 的大小关系将查找范围缩小一半。

由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 O(logn)，其中 n 是数组的长度。

二分查找的条件是查找范围不为空，即 left≤right。如果 target 在数组中，二分查找可以保证找到 target，返回 target 在数组中的下标。如果 target 不在数组中，则当 left>right 时结束查找，返回 −1。

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const mid = Math.floor((right - left) / 2) + left;
        const num = nums[mid];
        if (num === target) {
            return mid;
        } else if (num > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
};

复杂度分析

• 时间复杂度：O(logn)，其中 n 是数组的长度。

• 空间复杂度：O(1)。

reference