# Search Insert Position ### Source - lintcode: [(60) Search Insert Position](http://www.lintcode.com/en/problem/search-insert-position/) ### Problem Given a sorted array and a target value, return the index if the target isfound. If not, return the index where it would be if it were inserted inorder. 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 ### 題解 仍然是 [Binary Search](http://algorithm.yuanbin.me/zh-cn/basics_algorithm/binary_search.html) 中`lower_bound`的變形，兩大關鍵點：`start` 和`end` 的初始化；最終插入位置和`start` 以及`end` 之間的關系，由于`start`對應的索引一定是小于目標值的，那么`start + 1` 就是要求的值了，再檢查下兩端的邊界，DONE ### Java ~~~ public class Solution { /** * param A : an integer sorted array * param target : an integer to be inserted * return : an integer */ public int searchInsert(int[] A, int target) { if (A == null || A.length == 0) { return -1; } int start = -1, end = A.length; while (start + 1 < end) { int mid = start + (end - start) / 2; if (A[mid] == target) { return mid; // no duplicates } else if (A[mid] < target) { start = mid; } else { end = mid; } } return start + 1; } } ~~~ ### 源碼分析 分析三種典型情況： 1. 目標值在數組范圍之內，最后返回值一定是`start + 1` 1. 目標值比數組最小值還小，此時`start` 一直為`-1`, 故最后返回`start + 1` 也沒錯，也可以將`-1` 理解為數組前一個更小的值 1. 目標值大于等于數組最后一個值，由于循環退出條件為`start + 1 == end`, 那么循環退出時一定有`start = A.length - 1`, 應該返回`start + 1` 綜上所述，返回`start + 1`是非常優雅的實現。其實以上三種情況都可以統一為一種方式來理解，即索引`-1` 對應于在數組前方插入一個非常小的數，索引`end` 即對應數組后方插入一個非常大的數，那么要插入的數就一定在`start` 和`end` 之間了。 有時復雜的邊界條件處理可以通過『補項』這種優雅的方式巧妙處理。 ### 復雜度分析 時間復雜度 O(logn)O(\log n)O(logn), 空間復雜度 O(1)O(1)O(1).