索引の値

7833 ワード
アルゴリズム#アルゴリズム# テキストリンク

問題の説明


配列と数値を渡すsearch関数は、その数値に対応するインデックスの値を返します.渡された数値に対応するインデックスに値が存在しない場合は、-1を返します.伝達の配列は整然としている.
入力例は以下の通りです
search([1, 2, 3, 4, 5, 6], 4) // 3
search([1, 2, 3, 4, 5, 6], 6) // 5
search([1, 2, 3, 4, 5, 6], 11) // -1
この問題は一般に配列に対して1回のループの全体的な回転を行い,配列は最初から最後まで回転し,対応する数字を探す方式は時間的複雑度O(n)を有する.
つまり、配列全体をブラウズして、両方の1つを見つけたり見つけたりしません.
これに対する簡単な解決方法は以下の通りである.
function search(arr, val) {
  for (let i = 0; i < arr.length; i++) {
   if (arr[i] === val) {
    return i; 
   }
  }
  return -1;
};
環を持ち,O(n)の時間的複雑さを持つ.これを古祖魯線形探索と呼ぶ.
私たちが今回見なければならないのは少し違います.バイナリ検索を用いて問題を解くことは,分割と征服アルゴリズムを用いた方法である.
ソースコードは次のとおりです.
function search(array, val) {
 let min = 0;
 let max = array.length - 1;
  
 while (min <= max) {
    // 배열의 중간값을 취한다.
 	let middle = Math.floor((min + max) / 2);
    let currentElement = array[middle];
   
    // middle을 val과 비교하며 최신화한다. 
    // 효율적인 탐색을 위해 값이 존재하지 않을 부분은 바로 무시하는 방식을 취한다.
   	if (array[middle] < val) {
      min = middel + 1;
    }
    else if (array[middle] > val) {
      max = middle - 1; 
    }
    else {
      // middle의 값이 val과 같다면 리턴한다.
      return middle;
    }
 }
 // val에 해당하는 값이 없다면 -1을 리턴한다.
 return -1;
};
以上のように,分割征服アルゴリズムを用いることで時間を節約できる.以上のソースコードの時間的複雑度はLognである.
Leetcode - 506. Relative Ranks
22.04.14第2回Git/github講座