LeetCode33. 回転ソート配列の検索(C++)
1153 ワード
昇順で並べ替えられた配列が予め未知の点で回転していると仮定する.
(例えば配列[0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になる可能性がある).
指定したターゲット値を検索し、配列にターゲット値が存在する場合はインデックスを返します.そうでない場合は-1を返します.
配列に重複する要素が存在しないと仮定できます.
あなたのアルゴリズムの時間複雑度はO(log n)レベルでなければなりません.
例1:
入力:nums=[4,5,6,7,0,1,2]、target=0出力:4例2:
入力:nums=[4,5,6,7,0,1,2],target=3出力:-1
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/search-in-rotated-sorted-array
(例えば配列[0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になる可能性がある).
指定したターゲット値を検索し、配列にターゲット値が存在する場合はインデックスを返します.そうでない場合は-1を返します.
配列に重複する要素が存在しないと仮定できます.
あなたのアルゴリズムの時間複雑度はO(log n)レベルでなければなりません.
例1:
入力:nums=[4,5,6,7,0,1,2]、target=0出力:4例2:
入力:nums=[4,5,6,7,0,1,2],target=3出力:-1
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/search-in-rotated-sorted-array
class Solution {
public:
int search(vector& nums, int target)
{
int left=0,right=nums.size()-1;
while(left<=right)
{ int mid=left+right;
if(nums[mid]==target) return mid;
if(nums[left]<=nums[mid])
{
if(nums[left]<=target && target<=nums[mid])
right=mid-1;
else
left=mid+1;
}
else
{
if(nums[mid]<=target && target<=nums[right])
left=mid+1;
else
right=mid-1;
}
}
return -1;
}
};