リートコード33 回転ソートされた配列の検索 メモ

Medium

アイデア

• lognの時間複雑性については、バイナリサーチを使用する必要があります。
• 二等分して見つかった配列の中で、最も価値のある小さな点が、求めるべきピボット・ポイントです。
• バイナリサーチ

手続き

• 最初のバイナリ
• mid = l + / 2
• もし num[mid] > num[r] ならば、それは正常でないことを意味します。正常なソート配列は左が小さく、右が大きいはずですから、ピボットポイントが mid の右にあることを示しています。l = mid + 1 のように、l を右にシフトして絞り込みます；
• num[mid] <= num[r]の場合、正常であることを意味し、最小値はまだmidの左側にあります；
• 1回目の終了時、lの値は要求されたピボット
• ターゲットの値に基づいて、ターゲットを見つけるためにバイセクショ ンを実行する側を決定します。

代码

class Solution {
 public int search(int[] nums, int target) {
 if(nums.length == 0) return -1;
 
 int l = 0, r = nums.length - 1;
 while(l < r){
 int mid = l + (r - l) / 2;
 if(nums[mid] > nums[r]){
 l = mid + 1;
 }else{
 r = mid;
 }
 }
 
 
 int s = l;
 l = 0;
 r = nums.length - 1;
 if(target >= nums[s] && target <= nums[r]){
 l = s;
 r = nums.length - 1;
 }else{
 l = 0;
 r = s - 1;
 }
 
 while(l <= r){
 int mid = l + (r - l)/2;
 if(nums[mid] == target)
 return mid;
 else if(nums[mid] < target){
 l = mid + 1;
 }else{
 r = mid - 1;
 }
 }
 return -1;
 }
}

• reference:
• binary search
• 08/01/20