首页 > 代码库 > 【leetcode】Search in Rotated Sorted Array II
【leetcode】Search in Rotated Sorted Array II
Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
与I类似，只是在二分搜索前，只是在判断左右两边是否有序时更加麻烦一些。
此时复杂度是O(n)了，和采用线性搜索的方法基本一致
1 class Solution { 2 public: 3 bool search(int A[], int n, int target) { 4 5 6 int left=0; 7 int right=n-1; 8 int mid; 9 while(left<=right)10 {11 12 mid=(left+right)/2;13 if(A[mid]==target)14 {15 return true;16 }17 18 19 //增加了这些判断语句20 bool isLeft=true;21 22 for(int i=left;i<=mid;i++)23 {24 if(A[i]>A[mid])25 {26 isLeft=false;27 break;28 }29 }30 31 if(isLeft)32 {33 if(A[left]<=target&&target<A[mid])34 {35 right=mid-1;36 }37 else38 {39 left=mid+1;40 }41 }42 else43 {44 if(A[mid]<target&&target<=A[right])45 {46 left=mid+1;47 }48 else49 {50 right=mid-1;51 }52 }53 54 }55 return false;56 57 }58 };
【leetcode】Search in Rotated Sorted Array II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。