【宫水三叶の真题精选】好题拓展：运用二分找 target 首尾下标

朴素解法

一个朴素的解法是直接对 进行线性扫描，当第一次遇到 说明找到了答案。

代码：

import java.util.*;

public class Solution {
    public int search (int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }
}

• 时间复杂度：
• 空间复杂度：

二分

上述解法没有利用到数组有序的特性，利用元素有序的特性，我们可以使用「二分」来查找目标值。

但「二分」有一个比较容易混淆的点是：当需要找目标值第一次出现的下标时，条件应该写成 nums[mid] >= target 还是 nums[mid] <= target。

强记模板是没有意义的，我们需要搞清楚到底在「二分」什么：

由于二分是从中间开始找起的，所以找的必然是条件区间中靠近中心的的边界值。

文字不好理解，我们结合图片来看：

代码：

import java.util.*;

public class Solution {
    public int search (int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return -1;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return nums[r] == target ? r : -1;
    }
}

• 时间复杂度：
• 空间复杂度：

拓展（找首尾）

如果将问题进一步拓展，要求输出 在 中的「第一个」和「最后一个」位置 的话，该如何求解？

其实还是一样的，只需要抓住「二分」的本质即可：

显然，当我们想二分出「第一个」位置时，check 判断应该写成 nums[mid] >= target；而当二分出「最后一个」位置时，check 判断应该写成 nums[mid] <= target。

代码：

class Solution {
    public int[] search(int[] nums, int target) {
        int[] ans = new int[]{-1, -1};
        int n = nums.length;
        if (n == 0) return ans;

        // 第一次二分：求 target 第一次出现的位置
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (nums[l] != target) {
            return ans;
        } else {
            ans[0] = l;
            // 第二次二分：求 target 最后一次出现的位置
            l = 0; r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= target) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            } 
            ans[1] = l;
            return ans;
        }
    }
}

• 时间复杂度：
• 空间复杂度：

最后

这是我们「必考真题 の 精选」系列文章的第 No.105 篇，系列开始于 2021/07/01。

该系列会将牛客网中「题霸 - 面试必考真题」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)