Search for a Range

Question

Problem Statement

Given a sorted array of n integers, find the starting and ending position of
a given target value.

If the target is not found in the array, return [-1, -1].

Example

Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

Challenge

O(log n) time.

题解

Python

first/last position 结合。

  1. class Solution:
  2.     """
  3.     @param A : a list of integers
  4.     @param target : an integer to be searched
  5.     @return : a list of length 2, [index1, index2]
  6.     """
  7.     def searchRange(self, A, target):
  8.         ret = [-1, -1]
  9.         if not A:
  10.             return ret
  12.         # find the first position of target
  13.         st, ed = 0, len(A) - 1
  14.         while st + 1 < ed:
  15.             mid = (st + ed) / 2
  16.             if A[mid] == target:
  17.                 ed = mid
  18.             elif A[mid] < target:
  19.                 st = mid
  20.             else:
  21.                 ed = mid
  22.         if A[st] == target:
  23.             ret[0] = st
  24.         elif A[ed] == target:
  25.             ret[0] = ed
  26.         # find the last position of target
  27.         st, ed = 0, len(A) - 1
  28.         while st + 1 < ed:
  29.             mid = (st + ed) / 2
  30.             if A[mid] == target:
  31.                 st = mid
  32.             elif A[mid] < target:
  33.                 st = mid
  34.             else:
  35.                 ed = mid
  36.         if A[ed] == target:
  37.             ret[1] = ed
  38.         elif A[st] == target:
  39.             ret[1] = st
  41.         return ret

C++

  1. class Solution {
  2. public:
  3.     vector<int> searchRange(vector<int>& nums, int target) {
  4.         vector<int> result = {-1, -1};
  5.         if (nums.empty()) return result;
  7.         int lb = -1, ub = nums.size();
  8.         while (lb + 1 < ub) {
  9.             int mid = lb + (ub - lb) / 2;
  10.             if (nums[mid] < target) lb = mid;
  11.             else ub = mid;
  12.         }
  14.         if ((ub < nums.size()) && (nums[ub] == target)) result[0] = ub;
  15.         else return result;
  17.         ub = nums.size();
  18.         while (lb + 1 < ub) {
  19.             int mid = lb + (ub - lb) / 2;
  20.             if (nums[mid] > target) ub = mid;
  21.             else lb = mid;
  22.         }
  23.         result[1] = ub - 1;
  24.         return result;
  25.     }
  26. };

Java

lower/upper bound 的结合，做两次搜索即可。

  1. public class Solution {
  2.     /**
  3.      *@param A : an integer sorted array
  4.      *@param target :  an integer to be inserted
  5.      *return : a list of length 2, [index1, index2]
  6.      */
  7.     public int[] searchRange(int[] A, int target) {
  8.         int[] result = new int[]{-1, -1};
  9.         if (A == null || A.length == 0) return result;
  11.         int lb = -1, ub = A.length;
  12.         // lower bound
  13.         while (lb + 1 < ub) {
  14.             int mid = lb + (ub - lb) / 2;
  15.             if (A[mid] < target) {
  16.                 lb = mid;
  17.             } else {
  18.                 ub = mid;
  19.             }
  20.         }
  21.         // whether A[lb + 1] == target, check lb + 1 first
  22.         if ((lb + 1 < A.length) && (A[lb + 1] == target)) {
  23.             result[0] = lb + 1;
  24.         } else {
  25.             result[0] = -1;
  26.             result[1] = -1;
  27.             // target is not in the array
  28.             return result;
  29.         }
  31.         // upper bound, since ub >= lb, we do not reset lb
  32.         ub = A.length;
  33.         while (lb + 1 < ub) {
  34.             int mid = lb + (ub - lb) / 2;
  35.             if (A[mid] > target) {
  36.                 ub = mid;
  37.             } else {
  38.                 lb = mid;
  39.             }
  40.         }
  41.         // target must exist in the array
  42.         result[1] = ub - 1;
  44.         return result;
  45.     }
  46. }

源码分析

  1. 首先对输入做异常处理，数组为空或者长度为0
  2. 分 lower/upper bound 两次搜索，注意如果在 lower bound 阶段未找到目标值时，upper bound 也一定找不到。
  3. 取A[lb + 1] 时一定要注意判断索引是否越界！

复杂度分析

两次二分搜索，时间复杂度仍为 O(\log n).

Reference