网站会员体系方案,网站建设公司 上,wordpress交友模板,东西湖做网站LeetCode 704.二分查找 思路#x1f9d0;#xff1a; 在本篇以及之后几篇的博客中#xff0c;博主将会用二分法进行解答#xff0c;以此巩固二分题型。二分法一般用于具有二段性的数据中使用。比如该题为有序数组#xff0c;需要我们查找一个目标值target#xff0c;分析…LeetCode 704.二分查找 思路 在本篇以及之后几篇的博客中博主将会用二分法进行解答以此巩固二分题型。二分法一般用于具有二段性的数据中使用。比如该题为有序数组需要我们查找一个目标值target分析后发现这段数据中会出现三种情况大于target小于target等于target而等于target是我们的目标于是可以判断出这个数组是具有二段性的以target进行分段由此得出使用二分法。 我们以下面数组进行举例首先求出一个中间值这里我使用left (right - left) / 2求得中间值在某些情况下需要在right - left后面再加上1否则会导致死循环具体在之后的篇章中会进行说明。求出中间值nums[mid]3后此时target大于3于是可以得出[left,mid]之间的所有数据都不可能含有9则可以舍去这段区间得到left mid 1然后再次进行该过程。假如nums[mid] target则表示[mid,right]区间可以舍去则right mid - 1。当nums[mid] target时表示找到了目标值即可返回。如果left right表示整个数组都找完了也没找到目标值返回-1。 代码 class Solution {
public:int search(vectorint nums, int target) {int left 0;int right nums.size() - 1;while(left right){int mid left (right - left) / 2;if(target nums[mid])left mid 1;else if(target nums[mid])right mid - 1;else return mid;}return -1;}
};时间复杂度O(LogN) 空间复杂度O(1)
