題目連結: Binary Search

題目描述為給定一組已由小到大排序好的陣列 nums，以及目標數 target。
假如陣列中存在此數，則返回所在的 index，若不存在則返回 -1。
題目另外有補充3點 :
1.可假設此陣列中的元素都是唯一的。
2.陣列大小介於 [1, 10000]。
3.此陣列中元素大小介於 [-9999, 9999]。

思路1: 暴力法

我們可以從陣列中第一個元素開始比對，看是否與目標數 target 相同。找到則返回所在之 index。若直到最後一個元素均不相同，代表此陣列中不存在 target，返回 -1。
因為此陣列已由小到大排序過，當目前比較的數字已經 > target 時，表示接下來的數字也都會 > target。
因此我們可以停止往後找。

• 複雜度評估
  當陣列中有 Ｎ 個元素時，時間複雜度為 O(N)。
  此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func search(nums []int, target int) int {
 
    for i,v:=range nums{
        if target==v{
            return i
        }
        
        if v>target{
            return -1
        }
    }
    
	return -1
}

思路2： 二分搜尋法

因為此陣列已排序過，我們先比較陣列最中間的數與 target 的大小，若中間數 mid > target，表示陣列右半邊的數都 > target，只需要檢查陣列左半邊的數字即可。我們可以重複此流程，拿左半邊陣列最中間的數與 target 比較，每次減少一半需要查找的數字，直到搜索完成。其他情形同理。

• 複雜度評估
  當陣列中有 Ｎ 個元素時，因為每次減少一半需要查找的元素，最多只需要檢查 $\lceil \log_2 N \rceil + 1$ 次， 時間複雜度為 $O(\log N)$。
  此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func search(nums []int, target int) int {
 
	head := 0
	tail := len(nums) - 1
    middle := (head + tail) / 2
    
	for head <= tail {
        middle = (head + tail) / 2
		
		if nums[middle] == target {
			return middle
		} else if nums[middle] > target {
			tail = middle - 1
		} else {
			head = middle + 1
		}
	}
    
	return -1
}

小結

題目補充說明 1 讓我們不必檢查多組解的情形。
二分搜尋法處理邊界值以及溢位問題專業人士往往也犯錯，詳見 wiki 二元搜尋演算法條目下-實現中的問題，需要特別留意。補充說明 2 限制了陣列大小，讓我們不必擔心方法 2 中，取中間數的過程可能會造成溢位。 若此題沒有限制陣列大小時，我們需要稍微修改取中間數的方式為 middle = head+ (tail-head) / 2。
方法 2 即為本題希望我們採用的方法，與方法 1 比較，效率顯著提升。
舉例來說: 當陣列有 1025 個元素時，方法 1 最糟糕情形需要與 1025 個元素做比較，而方法 2 只需要比較 11 個元素。
此題也可以採用遞迴方式實現，基本概念一樣，只需要不斷更新目前搜尋範圍即可。
二元搜尋法對於在已排序的資料相當實用，之後會找幾題二元搜尋法的相關應用題目。

我將解法 2 修改為避免溢位的版本，以及實現了遞迴方式作為解法 3 並附上簡單的測試，上傳程式碼到此。