海边别墅

# 搜索算法

# 二分法/二分查找

二分法有查找精确值的，也有查找相对结果的，以下内容要注意区分场景。

先看一个小笑话：

有一天阿东到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把阿东拦下，要检查一下哪本书没有登记出借。阿东正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是阿东背着剩下的书走了。

从此，图书馆丢了 N - 1 本书。

# 二分细节

  1. 什么时候使用二分法？

    • 有序
    • 二段性，例如将数组分为两段连续子数组，check一段返回false，另一段返回true。
    • 某些内容有序，求解可以利用其相关的有序性质

  2. mid落点是在偏左还是偏右，两种情况下的意义是什么？

    让mid落在左右取决于除2：正常数除2，mid是落在偏左的，需要让其偏右可以将被除数先+1

    // mid落在偏左
mid = left + ((right-left)>>1);

// mid落在偏右，这里是关键，在被除数+1了。
mid = left + ((right-left+1)>>1)

    需要根据题意判断mid是靠左还是靠右，或是要直接找出mid。

  3. 循环条件是left<right还是left<=right? 分别都是使用在什么情况下的？

    left < right：循环终止条件为left==right，不会再走while中逻辑，漏掉了左右指针相等的场景，因此需要在while后面补上nums[left] == target ? left : -1;。

    left <= right：循环终止条件为left==right+1（==left+1），没有场景遗漏。但要注意：left、right赋值时不允许使用=mid，否则有死循环可能。

  4. 需要判断target == n[mid]直接返回mid吗？

    很多场景下并不是用二分法找到指定的某个结果，而是找到相对的结果。例如：力扣278题（第一个错误的版本）找到同类中第一个作为结果，这是没有办法直接得知mid是否满足结果，直到二分查找到最后才能知道。

  5. 什么时候left=mid，或left=mid+1；同样，什么时候right=mid，或right=mid-1？

    如果mid落点偏左，则移动left时，一定是需要真实移动的，也就是left=mid+1

    相反，mid落点偏右，right=mid-1。在查找相对结果时一定要注意。

    而check()能确认结果，则可以直接返回，且left、right都强制移动即可。

    当数组分为两部分，一部分符合要求，一部分不符合，为了找出符合要求的第一个数（有可能是左边最后一个，或右边第一个）

    • 只有一个结果值：靠左右无所谓，在while中判断是否==，return即可。
    • 右边部分符合，找出右边符合中的最小值：mid需要靠左，赋值时r=mid避免错过结果，l=mid+1
    • 左边部分符合，找出左边结果集中的最大值：mid靠右，赋值时l=mid避免错过结果，r=mid-1

  6. 二分查找的数组中只有一个数时，怎么做？

    看while条件是什么；可以提前判断，直接与target比较；也可以在最后兜底判断。

  7. 最后是返回-1还是left或right？

    一般根据题意，若查找不到返回-1时，则需要兜底返回-1；若是一定会存在查找结果，则可以返回left或right，具体还需要根据它们赋值时谁是用=mid。

  8. 二分区间如何定义，是[left, right]还是[left, right)？

    取决于两点：

    1. while(left ? right)，如果结果需要包含right，则必须<=（除非在最后兜底这种场景）；否则相反，不需要包含right，则使用<，当然，如果mid落点偏左，说不定可以兼容，而可以随便使用<或<=。
    2. mid落点是偏左还是偏右，可以决定是否能兼容区间大于结果区间的情况。

  9. 细节很多，需要如何组合这些细节处理？

    其实场景非常多变，最好的办法还是理解各种组合的场景，遇到具体场景多加分析，分析能力很关键。

细节代码分析：

当while(left<right)时：

func search(nums []int, target int) int {
    n := len(nums)
    l, r := 0, n-1
    for l < r {
        mid := l + ((r-l)>>1) // mid落点偏左
        if target == nums[mid] { // 判断了==，下面左右赋值时可以+1和-1
            return mid
        } else if target > nums[mid] { 
            l = mid+1
        } else {
            r = mid-1
        }
    }
    // 需要兜底处理：
    // 1.只有一个数的数组；
    // 2.剩下两个数且最后target>mid，left=mid+1，此时left=right不循环了，但left有可能等于target。
    // 3.剩下三个数且最后target!=mid，则left和right会移动到相等的位置，因此需要兜底再判断一次
    // 总结：由于while(left<right)，不包含等于，所以需要兜底判断
    if target == nums[l] {
        return l
    }
    return -1
}

当while(left<=right)时：

func search(nums []int, target int) int {
    n := len(nums)
    l, r := 0, n-1
    for l <= r {
        mid := l + ((r-l)>>1)
        if target == nums[mid] {
            return mid
        } else if target > nums[mid] {
            l = mid+1
        } else {
            r = mid-1
        }
    }
    return -1
}

# 二分查找模板

光有模板真的没用，碰到一些题目的边界问题要处理，如果不是真正理解模板中处理细节的含义，是没办法百分百AC的。

参考地址 (opens new window)

/* 注意：题目保证数组不为空，且 n 大于等于 1 ，以下问题默认相同 */
int BinarySearch(int array[], int n, int value)
{
    int left = 0;
    int right = n - 1;
    // 如果这里是 int right = n 的话，那么下面有两处地方需要修改，以保证一一对应：
    // 1、下面循环的条件则是 while (left < right)
    // 2、循环内当 array[middle] > value 的时候，right = middle

    while (left <= right)  // 循环条件，适时而变
    {
        int middle = left + ((right - left) >> 1);  // 防止溢出，移位也更高效。同时，每次循环都需要更新。
        if (array[middle] > value)
            right = middle - 1;
        else if (array[middle] < value)
            left = middle + 1;
        else
            return middle;
        // 可能会有读者认为刚开始时就要判断相等，但毕竟数组中不相等的情况更多
        // 如果每次循环都判断一下是否相等，将耗费时间
    }

    return -1;
}

int BinarySearch(int array[], int n, int value)
{
    int left = 0;
    int right = n - 1;

    while (left <= right)
    {
        int middle = left + ((right - left) >> 1);

        if (array[middle] >= value)  // 因为是找到最小的等值下标，所以等号放在这里
            right = middle - 1;
        else
            left = middle + 1;
    }

    if (left < n && array[left] == value)
        return left;

    return -1;
}

int BinarySearch(int array[], int n, int value)
{
    int left = 0;
    int right = n - 1;

    while (left <= right)  
    {
        int middle = left + ((right - left) >> 1);
      
        if (array[middle] >= value)
            right = middle - 1;
        else
            left = middle + 1;
    }
    
    return (left < n) ? left : -1;
}

# 二分相关题目

  • 275. H 指数 II
  • 153. 寻找旋转排序数组中的最小值
  • 33. 搜索旋转排序数组
  • 287. 寻找重复数
  • 704. 二分查找
  • 633. 平方数之和
  • 363. 矩形区域不超过 K 的最大数值和
  • 1482. 制作 m 束花所需的最少天数
  • 5764. 准时到达的列车最小时速（第 242 场周赛）
  • 374. 猜数字大小
  • 852. 山脉数组的峰顶索引
  • 167. 两数之和 II - 输入有序数组
  • 410. 分割数组的最大值
  • 剑指 Offer 53 - I. 在排序数组中查找数字 I
  • 875. 爱吃香蕉的珂珂
  • 1337. 矩阵中战斗力最弱的 K 行

# 手撕算法题

  1. 第一个错误的版本 (opens new window)

本题算是经典二分模板题，题目代码直接就是二分的模板。但做题一定要抛弃模板（或者说了解模板中每个细节），否则你迟早会死于其中细节的。

两种二分思路：1.找到第一个错误的版本 2.是找到最后一个正确的版本，那错误版本就是再+1即可。

找到第一个错误版本：也就是最左边的错误版本。当check(mid)发现是错误版本时，mid右边一定全是错误的，因此right必须往左边移动，那right=mid还是=mid-1呢？取决于while(left<right)和mid落点，当left<right，有right=mid，因为left=right时会退出while，而此时right是不断左移，最终一定是最左边的错误版本。

找到最后一个正确的版本：也就是最右边的正确版本。当check(mid)发现是正确版本时，mid左边一定全是正确版本，因此left必须右移。同上边结论，当left<right，left=mid，left不断右移，最终找到最后一个正确的版本，第一个错误版本在结果上+1即可。

各种场景下的代码是如何写的

找第一个错误版本(mid落点必须偏左)，while(left<right)：

// 区间为[1,n]
func firstBadVersion(n int) int {
    l, r := 1, n
    for l < r {
        mid := l + ((r-l)>>1)
        if isBadVersion(mid) {
            r = mid
        } else {
            l = mid+1
        }
    }
    return r
}

// 区间为[1,n+1]，同样兼容，因为right不断左移。
func firstBadVersion(n int) int {
    l, r := 1, n+1
    for l < r {
        mid := l + ((r-l)>>1)
        if isBadVersion(mid) {
            r = mid
        } else {
            l = mid+1
        }
    }
    return r
}

找第一个错误版本，while(left<=right)：

// 区间为[1,n]，同上面结论，同样兼容区间为[1,n+1]
func firstBadVersion(n int) int {
    l, r := 1, n
    for l <= r {
        mid := l + ((r-l)>>1)
        if isBadVersion(mid) {
            r = mid-1
        } else {
            l = mid+1
        }
    }
    return r+1
}

找最后一个正确版本（mid落点必须偏右），while(left<right)：

// 区间为[0,n]，由于l<r，无法取到l=r的场景，且兜底必须是l+1，所以区间不能为[1,n]
func firstBadVersion(n int) int {
    l, r := 0, n
    for l < r {
        mid := l + ((r-l+1)>>1)
        if isBadVersion(mid) {
            r = mid-1
        } else {
            l = mid
        }
    }
    return l+1
}

找最后一个正确版本，while(left<=right)：

// 区间[1,n]或着[0,n]都可以，因为落点偏右，left不断右移。
func firstBadVersion(n int) int {
    l, r := 1, n // 此处同样可以使用[0,n]
    for l <= r {
        mid := l + ((r-l+1)>>1)
        if isBadVersion(mid) {
            r = mid-1
        } else {
            l = mid+1
        }
    }
    return l
}

# DFS

同回溯算法

# BFS

把问题抽象成图，从一个点开始向四周扩散，一般使用队列辅助实现（借助先进先出特性一层一层遍历）。同时也经常用于解决最短、最小相关问题。

  • 单向bfs模板
// 计算从起点 start 到终点 target 的最近距离
public int bfs(Node start, Node target) {
	// 核心数据结构
    Queue<Node> q = new LinkedList<>();
    // 避免走回头路
    Set<Node> visited = new HashSet<>();
	// 将起点加入队列
    q.offer(start);
    // 记录扩散的步数
    visited.add(start);
    int step = 0;

    while (!q.isEmpty()) {
        int sz = q.size();
        // 将当前队列中的所有节点向四周扩散
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            // 常在这里处理站障碍物逻辑
            process();
            // 划重点：这里判断是否到达终点
            if (cur is target) {
                return step;
            }
            // 将 cur 的相邻节点加入队列
            for (Node x : cur.adj()) {
            	if (!visited.contains(x)) {
                    q.offer(x);
                    visited.add(x);
                }
            }
        }
        // 划重点：更新步数在这里
        step++;
    }
    
	return -1;
}
  • 双向bfs模板

只有当知道目标时才能从目标同时倒推。

private int bfs(String start, String target) {
    Set<String> q1 = new HashSet<>();
    Set<String> q2 = new HashSet<>();
    Set<String> visited = new HashSet<>();
    q1.add(start);
    q2.add(target);
    int step = 0;

    while (!q1.isEmpty() && !q2.isEmpty()) {
    	// 优化技巧：选取集合较小的开始遍历
    	// 集合元素多，扩散后的元素也越多，占用空间的增长速度更快，效率就越低
    	if (q1.size() > q2.size()) {
        	// 交换 q1 和 q2
        	Set<String> temp = q1;
        	q1 = q2;
        	q2 = temp;
        }
    
    	// q1,q2在遍历过程不能修改，用temp存储，事后再赋值给q1,q2
    	// temp代表当前一层的遍历结果
        Set<String> temp = new HashSet<>();

        for (String cur : q1) {
            // 处理障碍物逻辑
            process();
            if (q2.contains(cur)) {
                return step;
            }

            visited.add(cur);

            // 相邻节点加入
            for (Node x : cur.adj()) {
            	if (!visited.contains(x)) {
                    temp.add(x);
                    visited.add(x);
                }
            }
        }

        step++;
		// 技巧：由于需要前后双向遍历，避免冗余代码，交换变量即可
		// 本次遍历结果temp是q1的，由于要交换q1q2，
		// 所以将q1的东西给q2（即q2=temp），q2的给q1（q1=q2）
        q1 = q2;
        q2 = temp;
    }

    return -1;
}
修改于: 8/2/2021, 12:25:58 AM

← 散题汇总 →