[JavaScript]二分法、バイナリ検索、回転Array Search

二分法
二分法は非線形方程式(要するに複雑な方程式)の解(の近似値)の計算機を用いて解く方法である.アルゴリズムは以下の通りです.
f(x)=0の式で
1.初期区間[x 0,x 1]と誤差閾値epsilonを入力
2.x 0とx 1の関数値をそれぞれf(x 0)、f(x 1)と呼ぶ.
3.f(x 0)とf(x 1)の記号が異なる場合は、次の手順に進みます.(同じ場合は適用されません)
4.x 0とx 1の中間値をx 2に設定します.
5.誤差をx 0とx 1の差と呼ぶ場合、誤差がepsilonより小さい場合、x 2は有害である.誤差がepsilonより大きい場合は、下に進みます.
6.x 2の関数値はf(x 2)であり、誤差は半減する.
7.f(x 0)とf(x 2)の符号が異なる場合、x 1の値はx 2の値であり、f(x 1)の値はf(x 2)の値である.f(x 0)とf(x 2)の符号が同じである場合、x 0の値はx 2の値、f(x 0)の値はf(x 2)の値となる.すなわち範囲を狭める.
8.4回(2を設定するプロセス).
以上の手順で作成したコードは次のとおりです.

const Bisection = function (f,x0, x1, epsilon = Number.EPSILON) {
  fx0 = f(x0);
  fx1 = f(x1);
  if (fx0 * fx1 > 0) return 'wrong initial values';
  error = Math.abs(x1-x0);
  while (error > epsilon) {
    error = error / 2;
    x2 = (x0 + x1) / 2;
    fx2 = f(x2);
    if (fx0 * fx2 < 0) {
      x1 = x2;
      fx1 = fx2;
    } else {
      x0 = x2;
      fx0 = fx2;
    }
  }
  return x2;
}

console.log(x => x**2 - 3, 1, 2)
// 1.7320508075688774 (3의 양의 제곱근과 같다)

バイナリサーチ
バイナリ検索アルゴリズムはバイナリツリー検索を適用します.昇順配列の配列がある場合、配列内の要素のインデックスを検索する場合は、ゼロから検索するのではなく、中間を基準に半検索値を検索します.アルゴリズムは以下の通りです.

は左変数を宣言し、値は0です.

宣言

右変数、値は長さ-1です.(最終インデックス)

左

が右より大きくない場合は、中間変数を宣言し、左右の中間値に割り当てます(配列長が偶数の場合は整数部分のみを取ります).さもないと7日に行きます.

arr[media]が検索する値(target)と一致する場合、medialを返し、アルゴリズムを終了します.

targetをarr[middle]と比較し、arr[middle]がより大きい場合は右側範囲を1に縮小します.あるいは、左の範囲を一つ広げます.(検索範囲を縮小)

は、

3号を返します.

は、

-1を返します.

感覚アルゴリズムは二分法と少し似ている.二分法はまず区間を与え,その後区間を条件半減で解き,バイナリ探索法は先に区間を与え,次に条件に基づいてleftor rightを選択する方式である.バイナリ探索アルゴリズムを用いて,時間的複雑度をO(N)からO(logN)に激減させた.以下に、上記のアルゴリズムに従って作成されたコードを示します.

const binarySearch = function (arr, target) {
  // TODO : 여기에 코드를 작성합니다.
  let left = 0,
  right = arr.length - 1;
    while (left <= right) {
      let middle = parseInt((right + left) / 2);
      if (arr[middle] === target) {
        return middle;
      }
      if (target < arr[middle]) {
        right = middle - 1;
      } else {
      left = middle + 1;
      }
  	}
  return -1;
  
};
console.log(binarySearch([4, 6, 8, 9, 10, 15], 9)) // 3

Rotated Array Search
回転する配列探索バイナリ探索では,配列のみが少し変化した状態にある.配列は部分昇順状態であり、部分昇順状態とは、配列が0格子以上左または右に循環移動したときに、配列が完全に整列した状態にあることを意味する.回転状態なのでwhile文に検索基準を追加するだけです.既存のバイナリ検索ではtargetと中間インデックスのみを比較した.しかし,回転する配列では,既存のバイナリナビゲーションにおける配列と異なりarr[left]とarr[middle]の大きさ関係は明確ではない.したがって、まず左インデックスと中インデックスのサイズ関係を比較し、左インデックスとtarget、target、middleのサイズ関係を逐一比較します.次はコードです.

const rotatedArraySearch = function (rotated, target) {
  // TODO : 여기에 코드를 작성합니다.
  // 단순한 방법
  // return rotated.indexOf(target)

  // 이진 탐색 방법은 확실히 선형 방정식 이분법(bisection method)과 비슷...

  let left = 0;
  let right = rotated.length - 1;

  while (left <= right) {
    let middle = parseInt((left+right)/2);
    if (rotated[middle] === target) {
      return middle;
    }

    if (rotated[left] < rotated[middle]) {
      if (target < rotated[middle] && rotated[left] <= target) {
        right = middle - 1;
      } else {
        left = middle + 1;
      }

    } else {
      if (target <= rotated[right] && rotated[middle] < target) {
        left = middle + 1;
      } else {
        right = middle - 1;
      }
    }
    



  }  
  return -1;
};