二分搜尋法是計算機科學中常用的搜尋算法，它利用數組的有序性，通過每次將搜尋區間減半來快速定位目標值。下面將介紹三種不同的二分搜尋區間表示方式：左閉右閉區間（[left, right]）、左閉右開區間[left, right)、左開右開區間(left, right)。這些方法都可以用來實現C++中的lowerBound函數，即尋找第一個大於等於目標值的元素的索引。
目次
1. 左閉右閉區間 – [left, right]
C++
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)
C++
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)
C++
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;
}Time & Space Complexity
スクロールできます
| Time Complexity | Space Complexity |
|---|---|
| O(logn) | O(1) |
Related Topics
LC 34. Find First and Last Position of Element in Sorted Array
Note
Reference: 二分查找 红蓝染色法
三個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
コメント