外贸soho自己建站_广告牌样式图片大全_网络营销的现状分析_百度网站权重查询

题目

题目链接：https://leetcode.cn/problems/binary-search/
文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

class Solution {
public:int search(vector<int>& nums, int target) {}
};

题解思路

题目分析：

1. 数组：有序 -> 升序，元素不重复；
2. 返回值：成功 -> 下标，不成功 -> -1；
3. 基于以上可以采用二分法

二分法： 有 [left, right] 和 [left, right)两种，主要区别是 right 的取值

1. [left, right]：左闭右闭，right = nums.size() - 1， left == right有意义，所以while(left <= right)。
   • if (nums[mid] > target) ，说明需要更新 right，因为 区间是左闭右闭的，当前nums[mid] > target，说明nums[mid] 一定不是 target，即说明接下来搜索的区间是不包含该值的，所以 right = mid - 1；若right = mid的话，会导致mid这个对应的值又进入了下一轮的搜索。
   • if (nums[mid] < target) left = mid + 1;
   • if (nums[mid] = target) return mid;
2. [left, right)：左闭右开，right = nums.size()， left == right不合法，所以while(left < right)。
   • if (nums[mid] > target) ，说明需要更新 right，当前nums[mid] > target，说明接下来搜索的区间不包含nums[mid]的，由于区间是左闭右开的，更新后的搜索区间就是不包含right的，所以 right = mid；
   • if (nums[mid] < target) left = mid + 1;
   • if (nums[mid] = target) return mid;

代码

左闭右闭[left, right]

#include <vector>
#include <iostream>
using namespace std;class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{return mid;}}return -1;}
};
// @lc code=end
int main() {Solution obj;vector<int> vec = {0,2,3,6,8,9};int target = 6;int res = obj.search(vec, target);if(res != -1){cout << "成功success: " << res << endl;} else {cout << "fail: " << -1 << endl;}
}

时间复杂度：O(log n)
空间复杂度：O(1)

左闭右开[left, right)

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size(); while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > target){right = mid;}else if(nums[mid] < target){left = mid + 1;}else{return mid;}}return -1;}
};
// @lc code=end
int main() {Solution obj;vector<int> vec = {0,1,2,3,6,7,8,9,10,12};int target = 11;int res = obj.search(vec, target);if(res != -1){cout << "成功success: " << res << endl;} else {cout << "fail: " << -1 << endl;}
}