大厂面试真题详解:搜索区间-阿里云开发者社区

开发者社区> 算法编程> 正文

大厂面试真题详解:搜索区间

简介: 大厂面试真题详解:搜索区间

给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中,则返回[-1, -1]

在线评测地址:[领扣题库官网](https://www.lintcode.com/problem/search-for-a-range/?utm_source=sc-tianchi-sz-20oct
)

例1:

输入:
[]
9
输出:
[-1,-1]

例2:

输入:
[5, 7, 7, 8, 8, 10]
8
输出:
[3, 4]

算法:二分

思路

  • 由于给定的是一个有序数组,具有单调性,因此很容易想到二分。
  • 二分查找target的第一次出现的位置和最后一次出现的位置,最后输出即可。
  • 具体实现:
  • 对于一个长度为n的升序数组A,二分查找的区间为[0, n - 1],定义left = 0, right = n - 1,中间值mid = left + (right - left) / 2 。
  1. 当 A[mid] > target 时,显然这时查找数值偏大,说明答案在左区间,因此使 right = mid 来缩小查找数值。
  2. 当 A[mid] < target 时,显然这时查找数值偏小,说明答案在右区间,因此使 left = mid 来放大查找数值。
  3. 当 A[mid] == target 时,为了寻找target出现的最左端(第一次出现位置)时,我们选择左区间作为下一次二分区间,因此使 right = mid;为了寻找target出现的最右端(最后一次出现位置)时,我们选择右区间作为下一次二分区间,因此使 left = mid 。
  • 综上所述:
  • 当我们寻找target的左端点即第一次出现的位置时:
  1. 当 A[mid] < target 时, left = mid ;否则 right = mid。
  2. 最后优先判断并选取接近左边的 left 再判断 right
  • 当我们寻找target的右端点即最后一次出现的位置时:
  1. 当 A[mid] <= target 时, left = mid ;否则 right = mid。
  2. 最后优先判断并选取接近右边的 right 再判断 left

复杂度分析

  • 常数级别的额外空间,空间复杂度O(1)。
  • 两个二分,时间复杂度O(logn)。
public class Solution {
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: a list of length 2, [index1, index2]
     */
    // 寻找左端点
    static int findFirstTargetNum(int[] A, int target, int n){
        int left = 0, right = n - 1;
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            if (A[mid] < target){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        if (left < n && A[left] == target){
            return left;
        }
        if (right >= 0 && A[right] == target){
            return right;
        }
        return -1;
    }
    
    // 寻找右端点
    static int findLastTargetNum(int[] A, int target, int n){
        int left = 0, right = n - 1;
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            if (A[mid] <= target){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        if (right >= 0 && A[right] == target){
            return right;
        }
        if (left < n && A[left] == target){
            return left;
        }
        return -1;
    }
    
    public int[] searchRange(int[] A, int target) {
        int n = A.length;
        int[] interval = {-1, -1};
        interval[0] = findFirstTargetNum(A, target, n);
        interval[1] = findLastTargetNum(A, target, n);
        return interval;
    }
}

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接