当前位置: 代码迷 >> 综合 >> leetcode练习题 search-in-rotated-sorted-array-ii
  详细解决方案

leetcode练习题 search-in-rotated-sorted-array-ii

热度:1   发布时间:2023-12-15 09:55:49.0

解题思路

方法一、直接暴力搜索吧
方法二、若未旋转,则直接二分查找,若存在旋转,则找出分割点,在左右两个子数组分别进行二分查找。

代码

方法一、暴力搜索

class Solution {
public:bool search(int A[], int n, int target) {bool flag = false;for(int i = 0;i < n;i++){if(A[i] == target){flag = true;}}return flag;}
};

方法二、

class Solution {
public:bool search(int A[], int n, int target) {if(A[0] < A[n - 1])return binarySearch(A,0,n - 1,target);else{int i = 0;for(;i < n;i++){if(A[i] > A[i + 1])break;}return binarySearch(A,0,i,target) || binarySearch(A,i+1,n - 1,target);}}bool binarySearch(int A[],int low,int high,int target){bool flag = false;while(low <= high){int mid = (low + high) / 2;if(A[mid] == target){flag = true;break;}else if(A[mid] > target)high = mid - 1;elselow = mid + 1;}return flag;}
  相关解决方案