バイナリナビゲーションアルゴリズム

21/10/27:内容を変更しjsコードを追加

シーヶンスナビゲーション

まず順序探索を理解する.
特定のデータをブラウズし、前から順にデータを確認する方法.
資料の中でデータを探すときに最も一般的に使われています.
時間に余裕さえあれば、いつも欲しいデータを見つけることができます.

# python
for i in range(n):
    if array[i] == target:
        return i

// javascript
for (let i in arr) {
 if (arr[i] === target) {
   return i
 }
}

時間複雑度はO(N)であった.(最初から順番にナビゲートしていたので)
もしあなたが欲しいデータを探していて、データが揃えられているなら、どうなりますか?
検索するデータがデータの平均より大きい場合は、後で検索を開始します.
これにより、データが整列している場合、ナビゲーションが容易になります.

バイナリナビゲーション

中間データを検索データと比較します.
これは検索アルゴリズムで、検索するデータがもっと小さい場合は、前後と再比較します.
したがって,バイナリ検索を行うためにはソートが必要である.

プロセス

中間点を選択し、検索したデータより範囲を絞り込みます.O(logN)の時間的複雑さを有する.(実行ごとに半分に減る)
コンピュータエンジニアリングでは底部を省略したlogには2の底部がある.
バイナリ検索は,再帰的または繰返し文の2つの方法で実現できる.(実際、ほとんどがそうです)

実施方法

復帰する

# python
def binary_search(arr,target,start,end):
    if start>end: return None

    mid = (start+end)//2

    if arr[mid] == target:
        return mid
  
    elif arr[mid] > target:
        return binary_search(arr,target,start,mid-1)
  
    else:
        return binary_search(arr,target,mid+1,end)

arr = [2,4,5,6,9,10]
result = binary_search(arr,4,0,len(arr)-1)

print(result) # 1

// javascript
const binarySearch = (arr, target, start, end) => {
  if (start > end) return null;

  const mid = Math.floor((start+end) /2)
  const pivot = arr[mid];

  if (target === pivot) {
    return mid;
  }
  else if (target > pivot) {
    return binarySearch(arr,target,mid+1, end);
  }
  else {
    return binarySearch(arr,target, start,mid-1);
  }
}

const arr = [1,3,5,6,7,8,9,10];
const target = 8;

console.log(binarySearch(arr,target,0,arr.length-1)); // 6

複文

def binary_search2(arr,target,start,end):
  while start <= end:
    mid = (start+end)//2
    if arr[mid] == target:
      return mid

    elif arr[mid] > target:
      end = mid-1
    
    else:
      start = mid+1

  return None

arr2 = [2,4,5,6,9,10]
result = binary_search(arr2,9,0,len(arr2)-1)
print(result) # 4

ナビゲーション範囲が大きい場合にデータをソートした場合は、バイナリナビゲーションを試みます.