【LeetCode】search-in-rotated-sorted-array-2-----在旋转数组中搜索

xiaoxiao2021-02-28  10

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; } };
转载请注明原文地址: https://www.6miu.com/read-2350181.html

最新回复(0)