C++中的二分可以使用STL中的 std::binary_search()
、std::lower_bound()
和 std::upper_bound()
函数来实现,也可以手写实现。下面是手写实现的示例代码:
int binarySearch(vector<int>& nums, int target)
{
int left = 0, right = nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;// 找到了目标元素,返回下标
else if (nums[mid] < target) left = mid + 1; // 目标元素在右侧子数组中
else right = mid - 1; // 目标元素在左侧子数组中
}
return -1;// 没有找到目标元素,返回-1
}
在这个代码中,我们使用了二分法将数组分成两部分,并判断目标元素在哪一部分中。时间复杂度为O(log n),空间复杂度为O(1)。
Orz大佬 大早上就开整