leetcode不定期ブラシ問題---33.回転配列を検索

ソース:スナップリンク: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レベルでなければなりません.例1:

  : nums = [4,5,6,7,0,1,2], target = 0
  : 4

例2:

  : nums = [4,5,6,7,0,1,2], target = 3
  : 

クイズ:
一回のテーマを読んでから、大体の感じは配列の中から指定値の位置を見つけて戻ってきます.ないと-1に戻ります.そして直接書きます.

var search = function(nums, target) {
     return nums.indexOf(target);
};

運行後に開通しました.提出後も開通しました.実行時間は68 msで、メモリは33.7 MBを消費します.完璧なスタートですが、問題をよく調べてみると、問題の複雑さはO(log n)レベルでなければならないということです.二分法を使って作らなければならないという意味です.上の答えは意味がないです.では、改めて考え始めます.二分法は簡単です.毎回二分組で、条件に合う配列の中で次の二分検索を行います.配列を2つに分割した後、2つの可能性があり、一方が順序であり、一方が回転している場合は、左右の中間の間隔の値と2つの配列の両端値とを比較する必要がある.どの配列の中で探し続けるかを判断します.

  
nums = [4,5,6,7,8,9,0,1,2], target = 0

第一ステップ:配列の中間値を取って、配列を二分割します.

//       ：
left=0;
right = nums.length;
mid = ~~((left + right)/2)
//          mid=4
[4,5,6,7] 
8 
[9,0,1,2]

第二ステップ:mid値は両側の配列の先頭と比較します.
次のような場合があります.

nums[mid]==taget

中間値が目標値に等しい場合、直接midに戻ることができます.

nums[mid]target&nums[left]<=target

中間値が目標値targetより大きくて、左の配列の最初の値がtargetより小さいということは、左の配列が回転しているということであり、目標値はこの配列の中にあります.このときは左の配列で検索し続ける必要があります.このときはleftは変わらず、rightはmid-1になりました.

nums[mid]=taget

中間値は目標値targetより小さく、右の配列の最後の値がtargetより大きいということは、target値が右の配列にあることを示しているので、右の配列で引き続き検索する必要がある.この時leftはmid+1になり、rightは変わりません.

nums[mid]

nums[mid]target&nums[left]target

この2つの場合、どちらに値があるかは確定していないので、left＋1またはRight-1についてはさらに検索する.このようにして、最終的な値が分かります.再帰的にこの問題を解決することができる.
コードは以下の通りです.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
   var bs = (left,right)=>{
          const mid = ~~((left + right)/2);
          if(left > right)return - 1;
          if(nums[mid] === target){
              return mid;
          }else if(nums[mid]>target && nums[left] <= target){
              return bs(left,mid-1);
          }else if(nums[mid]>target && nums[left] > target){
              return bs(left+1,right);
          }else if(nums[mid]=target){
              return bs(mid+1,right);
          }else if(nums[mid]

    ：
    ：68ms
    ：33.9MB