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.
跟踪“旋转排序数组中的搜索”: 如果允许重复呢? 这会影响运行时的复杂性吗?怎么和为什么? 编写一个函数来确定给定的目标是否在数组中。
是search-in-rotated-sorted-array的衍射延伸,允许有重复数字出现。
class Solution { public: bool search(int A[], int n, int target) { if (n == 0) return false; int left = 0; int right = n - 1; while (left <= right) { int mid = (left + right) >> 1; if (A[mid] == target) return true; else if (A[mid] < A[right]){ if (A[mid] < target && A[right] >= target) left = mid + 1; else right = mid - 1; } else if (A[mid] >A[right]){ if (A[left] <= target&&A[mid]>target) right = mid - 1; else left = mid + 1; } else --right; } return false; } };