C++在旋转有序数组中怎么搜索
今天小编给大家分享一下C++在旋转有序数组中怎么搜索的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。
创新互联是一家集网站建设,长岛企业网站建设,长岛品牌网站建设,网站定制,长岛网站建设报价,网络营销,网络优化,长岛网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。
在旋转有序数组中搜索
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:
This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?
这道是之前那道 Search in Rotated Sorted Array 的延伸,现在数组中允许出现重复数字,这个也会影响我们选择哪半边继续搜索,由于之前那道题不存在相同值,我们在比较中间值和最右值时就完全符合之前所说的规律:如果中间的数小于最右边的数,则右半段是有序的,若中间数大于最右边数,则左半段是有序的。而如果可以有重复值,就会出现来面两种情况,[3 1 1] 和 [1 1 3 1],对于这两种情况中间值等于最右值时,目标值3既可以在左边又可以在右边,那怎么办么,对于这种情况其实处理非常简单,只要把最右值向左一位即可继续循环,如果还相同则继续移,直到移到不同值为止,然后其他部分还采用 Search in Rotated Sorted Array 中的方法,可以得到代码如下:
class Solution { public: bool search(vector& nums, int target) { int n = nums.size(), left = 0, right = n - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) return true; if (nums[mid] < nums[right]) { if (nums[mid] < target && nums[right] >= target) left = mid + 1; else right = mid - 1; } else if (nums[mid] > nums[right]){ if (nums[left] <= target && nums[mid] > target) right = mid - 1; else left = mid + 1; } else --right; } return false; } };
以上就是“C++在旋转有序数组中怎么搜索”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注创新互联行业资讯频道。
网站名称:C++在旋转有序数组中怎么搜索
新闻来源:http://myzitong.com/article/jephop.html