Search Insert Position

Question

Problem Statement

Given a sorted array and a target value, return the index if the target is
found. If not, return the index where it would be if it were inserted in
order.

You may assume NO duplicates in the array.

Example

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

Challenge

O(log(n)) time

题解

Python

问题可以转化为， 寻找first position that value is >= target。如果没找到， 那么就插入在list的尾部。

  1. class Solution:
  2.     """
  3.     @param A : a list of integers
  4.     @param target : an integer to be inserted
  5.     @return : an integer
  6.     """
  7.     def searchInsert(self, A, target):
  8.         if not A:
  9.             return 0
  10.         st, ed = 0, len(A) - 1
  11.         while st + 1 < ed:
  12.             mid = (st + ed) / 2
  13.             if A[mid] == target:
  14.                 ed = mid
  15.             elif A[mid] < target:
  16.                 st = mid
  17.             else:
  18.                 ed = mid
  19.         if A[st] >= target:
  20.             return st
  21.         elif A[ed] >= target:
  22.             return ed
  23.         else:
  24.             return len(A)

C++

  1. class Solution {
  2.     /** 
  3.      * param A : an integer sorted array
  4.      * param target :  an integer to be inserted
  5.      * return : an integer
  6.      */
  7. public:
  8.     int searchInsert(vector<int> &A, int target) {
  9.         // write your code here
  10.         if (A.empty()) return 0;
  12.         int n = A.size();
  13.         int lb = -1, ub = n;
  14.         while (lb + 1 < ub) {
  15.             int mid = lb + (ub - lb) / 2;
  16.             if (A[mid] < target) {
  17.                 lb = mid;
  18.             } else {
  19.                 ub = mid;
  20.             }
  21.         }
  22.         return ub;
  23.     }
  24. };

Java

仍然是 Binary Search 中lower_bound的变形，两大关键点：start 和end 的初始化；最终插入位置和start 以及end 之间的关系，由于start对应的索引一定是小于目标值的，那么start + 1 就是要求的值了，再检查下两端的边界，DONE

  1. public class Solution {
  2.     /**
  3.      * param A : an integer sorted array
  4.      * param target :  an integer to be inserted
  5.      * return : an integer
  6.      */
  7.     public int searchInsert(int[] A, int target) {
  8.         if (A == null || A.length == 0) {
  9.             return -1;
  10.         }
  12.         int start = -1, end = A.length;
  13.         while (start + 1 < end) {
  14.             int mid = start + (end - start) / 2;
  15.             if (A[mid] == target) {
  16.                 return mid; // no duplicates
  17.             } else if (A[mid] < target) {
  18.                 start = mid;
  19.             } else {
  20.                 end = mid;
  21.             }
  22.         }
  24.     return start + 1;
  25.     }
  26. }

源码分析

分析三种典型情况：

  1. 目标值在数组范围之内，最后返回值一定是start + 1
  2. 目标值比数组最小值还小，此时start 一直为-1, 故最后返回start + 1 也没错，也可以将-1 理解为数组前一个更小的值
  3. 目标值大于等于数组最后一个值，由于循环退出条件为start + 1 == end, 那么循环退出时一定有start = A.length - 1, 应该返回start + 1

综上所述，返回start + 1是非常优雅的实现。其实以上三种情况都可以统一为一种方式来理解，即索引-1 对应于在数组前方插入一个非常小的数，索引end 即对应数组后方插入一个非常大的数，那么要插入的数就一定在start 和end 之间了。

有时复杂的边界条件处理可以通过『补项』这种优雅的方式巧妙处理。

复杂度分析

时间复杂度 O(\log n), 空间复杂度 O(1).