# Binary Search Template

###### tags: `algorithm template` `c++` `Binary Search`

## 1. 左閉右閉區間 - [left, right]

int lowerBound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;  // 閉區間 [left, right]
    while (left <= right) {  // 區間不為空
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;  // [mid + 1, right]
        } else {
            right = mid - 1;  // [left, mid - 1]
        }
    }
    return left;
}

## 2. 左閉右開區間 - [left, right)

int lowerBound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();  // 閉區間 [left, right)
    while (left < right) {  // 區間不為空
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;  // [mid + 1, right)
        } else {
            right = mid;  // [left, mid)
        }
    }
    return left;  // right也可以, 指向同一個位置
}

## 3. 左開右開區間 - (left, right)

int lowerBound(vector<int>& nums, int target) {
    int left = -1;
    int right = nums.size();  // 閉區間 (left, right)
    while (left + 1 < right) {  // 區間不為空
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid;  // (mid, right)
        } else {
            right = mid;  // (left, mid)
        }
    }
    return right;
}

## Related Topics
### [34. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array)

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| | O(logn) | O(1) |

## Note
[Ref](https://www.bilibili.com/video/BV1AP41137w7/?spm_id_from=333.788&vd_source=088937f16fb413336c0cb260ed86a1c3)

三個lowerBound function都是求第一個>= target那個數的idx.
但有時候有時候給你nums及taget並不一定是求>=target的那個數的idx, 也有<, <=, >, 這四種情況是可以互相轉換的:
1. >= -> lowerBound(nums, target)
2. >  -> lowerBound(nums, target + 1)
3. <= -> lowerBound(nums, target) - 1
4. <  -> lowerBound(nums, target + 1) - 1