704. Binary Search

題目網址：https://leetcode.cn/problems/binary-search/

題意：給一已排序的整數 array nums, 用 binary search 找出 nums 中是否存在 target。若存在, 則返回該元素的 idx；否則, 返回 -1。

Solution：

想法：利用 Binary Search, 找到 left 為第一個 ≥ target 的數。若 left 越界 or nums[left] != target, 則代表 target 不存在於 nums 中

class Solution {
public:
    int search(vector<int>& nums, int target) {
        const int n = nums.size();
        int left = 0, right = n;

        while (left < right) {
            const int mid = left + (right - left) / 2;

            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        // 當 nums 中所有的元素都比 target 小 (target 不存在), left 會越界 (left = n)
        // 所以在存取 nums[left] 前, 要先判斷 left 是否越界, 否則存取會出錯
        return (left < n && nums[left] == target) ? left : -1;
    }
};

• time：$O(log(n))$ ➔ Binary Search
• space：$O(1)$ ➔ 只需常數空間