題目說明:給定一組排序過後的陣列和一個指定的值，如果該指定的值有被找到，則回傳該指定值的索引(Index)，若沒有的話則回傳要該指定值要被插入的索引值。
*演算法的時間要在O(log n)內

Case 1
Input: nums = [1,3,5,6], target = 5
Output: 2。原因：target是在此陣列的第二個

Case 2
Input: nums = [1,3,5,6], target = 2
Output: 1。原因：target要被插入在第一個的位置(1<2<3)

Case 3
Input: nums = [1,3,5,6], target = 7
Output: 4。原因：target要被插入在第四個的位置

解題思路：既然題目都給定排序過後的陣列以及時間要被限制在O(log n)，直覺反射就是用binary search(二分搜尋法)進行解題。

何謂Binary search?

1. 條件：給定的陣列(array)一定要經過排序
2. 設定三個變數(頭 head、尾 tail 以及中間索引 mid)來不斷找尋指定值(target)的索引(index)

• head:陣列的第0個位置
• tail:陣列的最後一個位置(陣列長度-1)
• mid:(頭+尾)/2取整數
• head要<=tail

3. 若陣列中間索引(array[mid])等於target，回傳mid
4. 若陣列中間索引(array[mid])小於target，head=mid+1，再次進行搜尋
5. 若陣列中間索引(array[mid])大於target，tail=mid-1，再次進行搜尋
6. 都沒有則回傳0(都沒找到target的index)
7. Recursive寫法(pseudo code)

BinarySearch(array,head,tail,target){
  mid=(head+tail)/2
  if(array[mid]==target){
      return mid
  }
  else if(array[mid]<target) {
      BinarySearch(array,mid+1,tail,target)
  }
  else {
      BinarySearch(array,head,mid-1,target)
  }
}

8. Iterative寫法(pseudo code)

BinarySearch(array,target){
  head=0
  tail=array.length-1
while (head<=tail){
  mid=(head+tail)/2
  if(array[mid]==target){
    return mid
    }
  else if(array[mid]>target){
    tail=mid-1
    }
  else {
    head=mid+1
  }
}
return 0;
}

Java

class Solution {
    public int searchInsert(int[] A, int target) {
        int low = 0, high = A.length-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(A[mid] == target) return mid;
            else if(A[mid] > target) high = mid-1;
            else low = mid+1;
        }
        return low;//因為此題都沒找到target要的index時要回傳的是要插入的index，故回傳low
}
}

Python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low=0
        high=len(nums)-1
        while(low<=high):
            mid=(low+high)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                high=mid-1
            else:
                low=mid+1
        return low#因為此題都沒找到target要的index時要回傳的是要插入的index，故回傳low