寻找食物储量题目描述你是一个冒险家在一个危机四伏的森林里你发现了一个隐藏的食物仓库。这个食物仓库由 n 个房间组成每个房间都有一定数量的食物。你需要找到第一个房间其中的食物数量大于或等于一个给定的值 x。这些房间是按食物数量升序排列的。你知道每个房间的食物数量但由于时间紧迫你不能一个个房间地去查找。因此你决定使用二分搜索来快速找到目标房间。你的任务是编写一个程序根据每个房间的食物数量和目标值 x输出第一个食物数量大于或等于 x 的房间的编号。解题思路这个是标准二分查找模板题构建一个二分查找函数最终返回值要加1。#include iostream #include vector using namespace std; //二分查找函数 int binary_search(int n, int target, vectorint nums){ int l 0; int r n - 1; int ans -1; //当左右指针未重合时 不断缩小空间 while(l r){ //保守做法 绝对不会出现越界 int mid l (r - l) / 2; //满足条件 if(nums[mid] target){ //右指针左移 缩小空间 r mid - 1; //记录答案 ans mid; } //不满足条件 左指针替换为mid右侧 else{ l mid 1; } } return ans; } int main(){ int n, x; cin n; vectorint nums(n); for(int i 0; i n; i){ cin nums[i]; } cin x; int ans binary_search(n, x, nums); if(ans ! -1){ //输出房间号需要加1 cout ans 1 endl; } else{ cout -1 endl; } return 0; }二分查找题目描述给定一个n个元素有序的升序整型数组nums和一个目标值target写一个函数搜索nums中的target如果target存在返回下标否则返回-1。你必须编写一个具有O(log n)时间复杂度的算法。解题思路标准二分查找和上一题有所不同的是这个是要查询到相等的元素因此需要额外一个相等的分支来判断。class Solution { public: int search(vectorint nums, int target) { int l 0; int r nums.size() - 1; while(l r){ int mid l (r - l) / 2; //判断相等的情况 如果相等直接return就行 if(nums[mid] target){ return mid; } else if(nums[mid] target){ r mid - 1; } else{ l mid 1; } } //没找到相等的元素 返回-1 return -1; } };在排序数组中查找元素的第一个位置和最后一个位置题目描述给你一个按照非递减顺序排列的整数数组nums和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target返回[-1, -1]。你必须设计并实现时间复杂度为O(log n)的算法解决此问题。解题思路这个题目要用到两次二分查找第一次查找左边界第二次查找右边界因此我写了一个函数用来查找两个边界这里return l和return r 1是完全等价的因为循环终止的条件就是l r此时只能是l r 1然后将target 1这样就可以找到右边界。class Solution { public: // 基础二分寻找第一个 target 的下标 int lower_bound(vectorint nums, int target) { int l 0, r nums.size() - 1; while (l r) { int mid l (r - l) / 2; if (nums[mid] target) { r mid - 1; } else { l mid 1; } } return l; } vectorint searchRange(vectorint nums, int target) { //左界限start int start lower_bound(nums, target); // 如果越界或者找到的数根本不是 target说明 target 不存在 if (start nums.size() || nums[start] ! target) { return {-1, -1}; } // 找 target 1 的左边界减 1 就是 target 的右边界 int end lower_bound(nums, target 1) - 1; return {start, end}; } };
