二分查找法的一些理解

发表于 更新于

前言

做到一道简单的二分题
感觉很多都忘了
记了忘，忘了记
往返循环

二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。
但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。百度百科

题型

题型基本是建立在有序数组的寻找上
就我碰到的有三种

  • 不重复数组找一个数K的索引
  • 可能重复数组找一个数K的最左边的索引
  • 可能重复数组找一个数K的最右边的索引

PS：这些题目的前提都是有序数组，并且是递增的

每次隔一阵子写就会出现莫名奇妙的死循环
不知道什么地方要加1
不知道判断要不要加=

所以写个帖子记录下
方便之后回忆

一般的二分查找法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @param nums           寻找的数组
* @param target         寻找的目标值
* @returns {number}     目标位置索引
*/
function binarySearch(nums, target) {
    var length = nums.length;
    var left = 0;
    var right = length - 1;
    var mid = 0;
    while (left < right) {
        mid = (left + right + 1) >>> 1;
        if (target >= nums[mid]) {
            // 如果目标值 >= mid对应的值，推出目标值处于右半区，且包括mid这个点
            // 更新左边界
            left = mid;
        }
        else if (target < nums[mid]) {
            // 如果目标值 < mid对应的值，推出目标值处于左半区，且不包括mid这个点
            // 更新右边界
            right = mid - 1;
        }
    }
    return nums[left] === target ? left : -1;
}

不重复数组找K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* @param nums           寻找的数组
* @param target         寻找的目标值
* @returns {number}     目标位置索引
*/
function binarySearch(nums, target) {
    var length = nums.length;
    var left = 0;
    var right = length - 1;
    var mid = 0;
    while (left < right) {
        mid = (left + right) >>> 1;
        if (target === nums[mid]) {
            // 找到，返回索引
            return mid;
        }
        else if (target > nums[mid]) {
            // 没找到，且目标值 > mid对应的值，推出此时值处于右分区
            // 更新左边界
            left = mid + 1;
        }
        else if (target < nums[mid]) {
            // 没找到，且目标值 < mid对应的值，推出此时值处于左分区
            // 更新右边界
            right = mid - 1;
        }
    }
    return nums[left] === target ? left : -1;
}

重复数组找K的最左边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* @param nums           寻找的数组
* @param target         寻找的目标值
* @returns {number}     目标位置索引
*/
function binarySearch(nums, target) {
    var length = nums.length;
    var left = 0;
    var right = length - 1;
    var mid = 0;
    while (left < right) {
        mid = (left + right) >>> 1;
        if (target > nums[mid]) {
            // 如果目标值 > mid对应的值，推出目标值在右分区，且不包括mid这个点
            // 更新左边界
            left = mid + 1;
        }
        else if (target <= nums[mid]) {
            // 如果目标值 <= mid对应的值，推出目标值在左分区
            // 此时如果是小于的话，表明在左分区，不包括mid这个点
            // 此时如果是等于的话，表明找到，但是不确定是不是最左边的，所以也要搜索左分区
            // 更新右边界
            right = mid;
        }
    }
    return nums[left] === target ? left : -1;
}

重复数组找K的最右边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* @param nums           寻找的数组
* @param target         寻找的目标值
* @returns {number}     目标位置索引
*/
function binarySearch(nums, target) {
    var length = nums.length;
    var left = 0;
    var right = length - 1;
    var mid = 0;
    while (left < right) {
        // 右边界收缩，所以用右中位数
        mid = (left + right + 1) >>> 1;
        if (target < nums[mid]) {
            // 如果目标值 < mid对应的值，推出目标值在左半区，且不包括mid这个点
            // 更新右边界
            right = mid - 1;
        }
        else if (target >= nums[mid]) {
            // 如果目标值 >= mid对应的值，推出目标值在右半区
            // 此时如果是大于的话，表明在右分区，且不包括mid这个点
            // 此时如果是等于的话，表明找到，但是不确定是不是最右边的，所以也要搜索右分区
            // 更新左边界
            left = mid;
        }
    }
    return nums[left] === target ? left : -1;
}

后记

越是简单感觉越容易写错emmm