Follow up for "Search in Rotated Sorted Array":What ifduplicatesare allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
题意：一个已经排序过得有重复元素的数组翻转后查找target。
思路：每次判断A[left],A[mid],A[right]的关系，然后找到确定是递增的部分接着二分，，也有特殊情况就是left++,right–
class Solution {public:bool search(int A[], int n, int target) {int left = 0, right = n-1;while (left <= right) {int mid = left + (right – left) / 2;if (A[mid] == target) return true;if (A[left] < A[mid]) {if (A[left] <= target && target < A[mid])right = mid – 1;else left = mid + 1;} else if (A[mid] < A[right]) {if (A[mid] < target && target <= A[right])left = mid + 1;else right = mid – 1;} else if (A[left] == A[mid]) left += 1;else if (A[right] == A[mid]) right -= 1;}return false;}};
躲在墙角、掩藏那孤独而又不奢怜悯的伤…
