## [704\. Binary Search](https://leetcode.com/problems/binary-search/)

Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return `-1`.

You must write an algorithm with `O(log n)` runtime complexity.

**Example 1:**

**Input:** nums = \[-1,0,3,5,9,12\], target = 9
**Output:** 4
**Explanation:** 9 exists in nums and its index is 4

**Example 2:**

**Input:** nums = \[-1,0,3,5,9,12\], target = 2
**Output:** -1
**Explanation:** 2 does not exist in nums so return -1

**Constraints:**

- `1 <= nums.length <= 104`
- `-104 < nums[i], target < 104`
- All the integers in `nums` are **unique**.
- `nums` is sorted in ascending order.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // [左邊界, 右邊界] = [0, n - 1]
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;
                // 當 nums[mid] 比 target 小的時候，代表搜尋的值在右側，所以 ++left
            } else if(nums[mid] < target) {
                ++left;
                // 當 nums[mid] 比 target 大的時候，代表搜尋的值在左側，所以 --right
            } else {
                --right;
            }
        }
        return -1;
    }
};