# LeetCode 704. Binary Search (元素重複)
[LeetCode 704. Binary Search #](leetcode_url) (難度 通過率)
<!--
(<font color=#00AF9B>Easy</font> 53.8%)
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
-->

- 限制 :

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

- Solution

解法相同，但是要往回推到最前面的值，所以不能直接 return index，要慢慢往前找。這樣的找法複雜度就會變高 ($f(n) = lg(n) + n = O(n)$)，或者要再寫一個 binary search 也可以再降低。(但我懶惰，先不寫)
- 時間複雜度: $O(n)$
- 空間複雜度: $O(1)$

- 程式碼

    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) break;
                else if(nums[temp_index] < target) min_index = temp_index + 1;
                else if(nums[temp_index] > target) max_index = temp_index - 1;
            }
            while(temp_index > 0 && nums[temp_index - 1] == target)
            {
                temp_index--;
            }
            if(nums[temp_index] == target) return temp_index;
            return -1;
        }
    };

</details>