題目連結: https://leetcode.com/problems/binary-search/

參考解法: https://leetcode.com/problems/binary-search/discuss/423162/Binary-Search-101

解法一:

    func search(_ nums: [Int], _ target: Int) -> Int {
        if nums.count == 0 { return -1 }
        var left = 0
    	var right = nums.count - 1
    	while left <= right {
    		let mid = (left + right) / 2
    		if nums[mid] == target {
    			return mid
    		} else if nums[mid] < target {
    			left = mid + 1
    		} else {
    			right = mid - 1
    		}
    	}
    	return -1
    }

解法二:

func search(_ nums: [Int], _ target: Int) -> Int {
    if nums.count == 0 { return -1 }
    var left = 0
    var right = nums.count - 1
    while left < right {
        let mid = left + (right - left + 1) / 2
        if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid
        }
    }
    return nums[left] == target ? left : -1
}

Rule of thumb when it comes to binary search: (Note: below is from Ref)

1. Include ALL possible answers when initialize lo & hi
2. Don’t overflow the mid calculation
3. Shrink boundary using a logic that will exclude mid
4. Avoid infinity loop by picking the correct mid and shrinking logic
5. Always think of the case when there are 2 elements left

Ref: https://leetcode.com/problems/binary-search/discuss/423162/Binary-Search-101