二分查找算法题

笔记篇,看的掘金文章

神三元大佬的二分查找

空间复杂度O(1),时间复杂度O(lgn)

注意二分查找要求 必须 数据有序 无重复,换句话说 单增 或 单减
且最好是 数组,因为数组随机访问时间复杂度为O(1),
链表则为O(n),链表二分查找时间复杂度为O(nlgn)

基本二分查找

题目

给定一个无重复的有序整型数组,数组大小在 [1,10000] 之间,

查找目标数 target 在数组中的索引,不存在则返回 -1。

思路

1、一开始,数组范围是整个原数组；

2、将目标数与数组的中位数比较,如果中位数等于目标数,则返回

如果中位数大于目标数,则抛弃数组的后半部分,反之抛弃前半部分；

3、重复这个过程,直到找到目标数 t 或者数组范围为空为止。

标准解法

let search = (arr, target) => {
    let left = 0;
    let right = arr.length-1;
    while(left <= right) {
        let mid = (left + right) >>> 1;
        if(arr[mid] == target) return mid
        else if(target < arr[mid]) { right = mid - 1; }
        else if(target > arr[mid]) { left = mid + 1 }
    }
    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;
}

mid = left + (right - left) / 2 防止溢出
mid = left + (right - left >> 1) 最终完美写法

搜索插入位置(leetcode 35)

leetcode

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

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

leetcode

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

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

搜索旋转排序数组

leetcode

// 只在有序那边找
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
};