704 Binary Search

• 在排序陣列中找到目標值，若存在回傳 index，不存在回傳 -1。
• kotlin

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size - 1
        while (left <= right) {
            val mid = left + (right - left) / 2
            when {
                nums[mid] == target -> return mid
                nums[mid] < target -> left = mid + 1
                else -> right = mid - 1
            }
        }
        return -1
    }
}

• follow up
  • 如果陣列有重複值，要找第一個或最後一個出現的 index？（改成 lower_bound / upper_bound）
  • 如果資料是無限流（Infinite Array Search），如何應對？（先 exponential search 找邊界，再 binary search）
  • 如果陣列大小非常大，如何降低 磁碟 IO 或網路存取次數？（B-Tree / 分段 binary search）