目標：
這題主要目的在於了解如何處理以排序陣列的快速方法：二元搜尋法。

原題：

Question:
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:
Input: [1,3,5,6], 5
Output: 2

Example 2:
Input: [1,3,5,6], 2
Output: 1

Example 3:
Input: [1,3,5,6], 7
Output: 4

Example 4:
Input: [1,3,5,6], 0
Output: 0

分析/解題：
給定一個排序的陣列和目標值，假定陣列的數字不會重複。
題目要求找到目標值在這個陣列中的位置；
若無，則回傳如果要將其插入時，應插入的位置。

這題是很典型的二元搜索法(Binary Search)。
所謂的Binary Search，就是資料已處於被排序的狀態，
那麼在這些資料內搜索某個特定值就不用一個一個找，
我們可以用比較快的方法來搜尋。

假設我們有一組排序過的陣列，
搜尋的第一步就是取得中間點的那個值，我們先稱之為mid，
那mid左邊的數必然小於mid，反之mid右邊的數必然大於mid。
(按順序排的嘛XD)
所以我們拿目標值target跟mid比較，
如果target == mid，那mid所在的位置就是我們要的答案；
如果target > mid，表示答案只可能在mid右邊到尾端之間(不含mid)；
如果target < mid，表示答案只可能在mid左邊到開頭之間(不含mid)。
如此一來，每次取得區塊的中間點的值，並和target做比較，
則每次都可以至少刪掉一半的可能的數量，
直到找到答案(target == mid)，
或是區塊上下限交錯(那就表示target不存在於陣列之中)，
我們同樣可以將下限的index輸出，因為它就代表應該被插入的點。

例1. nums=[1,3,5,6], target=2
首先取下限lo = 0, 上限up = 3(頭跟尾), 中間點mi = (lo + up) / 2 = 1 ->
nums[1]為3, 3 > 2 -> 將up改為mi-1=0 -> mi = (0 + 0) / 2 = 0 ->
nums[0]為1, 1 < 2 -> 將lo改為mi+1=1 ->
lo和up已交叉，故結果應輸出1。

中間的值的變化如下：

lo  up  mi  nums[mi]
0   3   1   3
0   0   0   1
1   0   0   1

例2. nums=[1,3,5,6], target=5
首先取下限lo = 0, 上限up = 3(頭跟尾), 中間點mi = (lo + up) / 2 = 1 ->
nums[1]為3, 3 < 5 -> 將lo改為mi+1=2 ->mi = (2+3)/2 = 2 ->
nums[2]為5, 5==5 -> 直接輸出mi的值2即是答案。

中間的值的變化如下：

lo  up  mi  nums[mi]
0   3   1   3
2   3   2   5

下面也列出[1,3,5,6], 7跟[1,3,5,6], 0的值變化的過程，
有興趣或對整個邏輯還沒有弄得很明白的讀者可以嘗試推導一遍。

nums=[1,3,5,6], target=7 -> ans = 4

lo  up  mi  nums[mi]
0   3   1   3
2   3   2   5
3   3   3   6
4   3   3   6

nums=[1,3,5,6], target=0 -> ans = 0

lo  up  mi  nums[mi]
0   3   1   3
0   0   0   1
0   -1  -1  6        #(這個是用python輸出的，所以nums[-1] == 6)

底下的解法看個人喜好命名均可。

Java:

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int i = 0, j = nums.length-1;
        int index = -1;
        while(i <= j) {            
            index = (i + j) / 2;  
            if(nums[index] == target)
                return index;
            if(nums[index] >= target)
                j = index - 1;
            else
                i = index + 1;          
        }
        return i;
    }
}

Python:

class Solution:
    def searchInsert(self, nums: 'List[int]', target: 'int') -> 'int':
        lo, up = 0, len(nums) - 1
        mi = (lo + up) // 2
        while lo <= up:
            if nums[mi] == target: 
                return mi
            elif nums[mi] > target:
                up = mi - 1
            else:
                lo = mi + 1            
            mi = (lo + up) // 2
        return lo

在這個解題過程，由於每次我們都會將範圍縮小一半，
所以總共比對的次數就相當於求這個陣列的長度是2的幾次方，
故時間複雜度為O(logN)。
(電腦科學領域的對數一般不特別提的話通常是以2為底)

事實上，Java中也有提供 Arrays.binarySearch(int[] a, int key)
於utils的函式庫中，但有一點不一樣的是，當找不到target的時候，
如果插入該key所在位置為index，則回傳值為**-index-1**。
取負號是為了和key存在於陣列的狀況做分隔，
額外減1則是為了將key在0的位置及key應該要插入在0的位置做區分。
(因為0取負號還是0)

Binary Search是在排序陣列或一些有序的資料結構中很常用到的演算法，
以後在談到**二元搜尋樹(BST, Binary Search Tree)**的時候也會用到它。
所以如何寫一個二元搜尋的簡單方法是很有用的，可以的話務請熟練XD

面試實際可能會遇到的問題：
「(Java)如果上限接近Integer.MAX_VALUE的話相加有overflow的可能？」
(將(lo+up)/2改成lo + (up-lo)/2，可以保證不會溢出)

「時間/空間複雜度？」
(O(logN), O(1))

「我想知道到底結果target是否存在array中，但不想額外加回傳的值？」
(如上面提到的，將插入的狀況改為**-index-1**來表達)

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0053. Maximum Subarray (Easy)