二分查找算法题

二分查找算法题

注意二分查找要求 必须 数据有序 无重复,换句话说 单增 或 单减

且最好是 数组,因为数组随机访问时间复杂度为O(1),

链表则为O(n),链表二分查找时间复杂度为O(nlgn)

704. 二分查找

https://leetcode.cn/problems/binary-search/description/

标准解法

var search = function (nums, target) {
    let left = 0, right = nums.length - 1
    while (left <= right) {
        // 二进制整体右移一位，原本最右的一位删除，相当于除以2向下取整
        const mid = left + ((right - left) >> 1)
        if (target < nums[mid]) {
            right = mid - 1
        } else if (target > nums[mid]) {
            left = mid + 1
        } else {
            // 所以上面可以放心去掉mid点，因为如果mid===target，此处已经结束了
            return mid
        }
    }
    return -1
};

记住 left <= right right = mid - 1; left = mid + 1

递归解法

let search = (nums, target) => {
    let helpSearch = (nums, left, right, target) => {
      if(left > right) return -1;
      let mid = (left + right) >>> 1;
      if(nums[mid] == target) return mid;
      else if(nums[mid] > target) 
        return helpSearch(nums, left, mid - 1, target);
      else 
        return helpSearch(nums, mid+1, right, target);
    }
    return helpSearch(nums, 0,  nums.length - 1, target);
}

记住 helpSearch = (nums, left, right, target)

相当于不断二分,由一条路走到黑,再一路返回结果

标准解法里可以做一些修改,省点代码

let search = (arr, target) => {
    let begin = 0;
    let end = arr.length; // 这里不-1
    while(begin < end) { // 这里也不写=
        let mid = (begin + end) >>> 1;
        if(arr[mid] == target) { return mid; }
        // 这里也不用-1,因为while那里无=,所以最后一个right不会被包括进去
        else if(arr[mid] > target) { end = mid; }
        // left则需要+1,因为left会被包括进去
        else if(arr[mid] < target) { begin = mid + 1; }
    }
    return -1;
}

27. 移除元素

https://leetcode.cn/problems/remove-element/description/

var removeElement = function (nums, val) {
    // 思路就是把不等于val的数一个个在前面排好
    let p = 0
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== val) {
            nums[p++] = nums[i]
        }
    }
    return p
};

26.删除排序数组中的重复项
283.移动零
844.比较含退格的字符串

977.有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/description/

var sortedSquares = function (nums) {
    // 用指针p2指向平方后数的最终位置，p为从后向前移动，因为最大数的数在后面
    // 用新数组来接答案
    // Math.sqrt 平方根, Math.pow x次方
    let p1 = 0, p2 = nums.length - 1
    let res = new Array(nums.length).fill(0), k = nums.length - 1
    while (p1 <= p2) {
        const p1Sqrt = nums[p1] * nums[p1]
        const p2Sqrt = nums[p2] * nums[p2]
        if (p1Sqrt > p2Sqrt) {
            res[k--] = p1Sqrt
            p1++
        } else {
            res[k--] = p2Sqrt
            p2--
        }
    }
    return res
};

209.长度最小的子数组

https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

59.螺旋矩阵II

35.搜索插入位置

https://leetcode.cn/problems/search-insert-position/description/

var searchInsert = function(nums, target) {
    let left = 0
    let right = nums.length - 1
    while(left <= right) {
        let mid = left + (right - left >> 1)
        if(nums[mid] === target) return mid
        else if(nums[mid] < target) { left = mid + 1}
        else if(nums[mid] > target) { right = mid - 1}
    }
    return left
};

34.在排序数组中查找元素的第一个和最后一个位置

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

这个应该是最强又最好理解的解法了

var searchRange = function(nums, target) {
    let left = 0,right = nums.length -1
    let l = 0,r = nums.length -1

    // 这里的left就会是左边界
    while(left <= right) {
        let mid = (left + right) >> 1
        if(nums[mid] < target) {
            left = mid + 1
        } else if(nums[mid] >= target) {
            right = mid - 1
        }
    }

    // 这里的r就会是右边界
    while(l <= r) {
        let mid = (l + r) >> 1
        if(nums[mid] <= target) {
            l = mid + 1
        } else if(nums[mid] > target) {
            r = mid - 1
        }
    }
    return nums[left] === target && nums[r] === target? [left,r] : [-1,-1]
};

33.搜索旋转排序数组

https://leetcode.cn/problems/search-in-rotated-sorted-array/description/

// 只在有序那边找
var search = function(nums, target) {
    let l = 0,r = nums.length - 1
    while(l <= r) {
        let mid = l + (r - l >> 1)
        if(nums[mid] === target) { return mid }
        else if(nums[l] <= nums[mid]) {
            if(nums[l] <= target && target <= nums[mid]) { r = mid - 1 }
            else { l = mid + 1 }
        } else {
            if(nums[mid] <= target && target <= nums[r]) { l = mid + 1 }
            else { r = mid - 1 }
        }
    }
    return -1
};

带注释版

// 只在有序那边找
var search = function(nums, target) {
    let l = 0,r = nums.length - 1
    while(l <= r) {
        let mid = l + (r - l >> 1)
        if(nums[mid] === target) { return mid }
        // 先找有序区间，再在有序区间内二分查找
        else if(nums[l] <= nums[mid]) { // 说明左边为有序区间,注意这里得是 <=, mid 可能= l
             // 此时不能像二分排序一样简单判断 target <= mid,还需判断 target>=左边界
             // 因为经过旋转后 左边的数不一定是最小的数
             // 总之核心就是确定target的区间
            if(nums[l] <= target && target <= nums[mid]) {
                r = mid - 1
            } else {
                l = mid + 1
            }
        } else { // 右边为有序区间
            // 比一般二分查找多了一步 先判断有序区间
            // 假设当前循环已经在有序区间内，但却target在mid右侧
            // 当前循环会判断mid左侧为有序区间，进入上一分支，
            // 然后再上一分支内发现 target不属于左侧区间，缩小范围到右侧区间
            // 进入第二次循环，新mid之后，由于左侧有序，又只判断左侧区间....
            // 所以只要一进入有序区间，从头到尾就只找了左边的
            if(nums[mid] <= target && target <= nums[r]) {
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
    }
    return -1
};