---
# System prepended metadata

title: LeetCode 704. Binary Search
tags: [Leetcode]

---

# LeetCode 704. Binary Search

[LeetCode 704. Binary Search](https://leetcode.com/problems/binary-search/) (<font color=#00AF9B>Easy</font> 57.2%) 

- 限制 :

    <ul>
    <li><code>1 <= nums.length <= 10^4</code></li>
    <li><code>-10^4 < nums[i], target < 10^4</code></li>
    <li><code>All the integers in nums are unique</code></li>
    <li><code>nums is sorted in ascending order</code></li>
    </ul>

- Solution

    基本的 binary search ，只不過不知道為啥都忘光了QQ
    - 時間複雜度: $O(lg(n))$
    - 空間複雜度: $O(1)$

- 程式碼
    ```c++=
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int min_index = 0, max_index = nums.size()-1;
            int temp_index = (min_index + max_index)/2;

            // 這裡要設 <= 的原因是因為大小邊界有可能一樣，不可以先跳，這樣就會對
            while(min_index <= max_index)
            {
                // 這裡要寫的是 (max - min) / 2 + min 才對，不可以直接相減
                temp_index = (max_index - min_index) / 2 + min_index;
                cout << min_index << ' ' << temp_index << ' ' << max_index <<'\n';
                if(nums[temp_index] == target) return temp_index;
                else if(nums[temp_index] < target) min_index = temp_index + 1;
                else if(nums[temp_index] > target) max_index = temp_index - 1;
            }
            return -1;
        }
    };

    ```