資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時裝設計
法學用 JavaScript 實現塊搜尋
塊搜尋
就像二分查詢，塊搜尋也是一個用於排序陣列的搜尋演算法。基本思想是透過固定步進或跳過某些元素而不是搜尋所有元素來檢查更少的元素（比線性搜尋）。
例如
假設我們有一個長度為 n 的陣列 arr 和大小為 m 的塊（要跳過）。然後我們從索引 arr[0]、arr[m]、arr[2 * m]、...、arr[k * m] 等進行搜尋。
一旦我們找到區間 arr[k * m] < x < arr[(k+1) * m]，我們就從索引 k * m 開始執行線性搜尋操作以找到元素 x。
該演算法的時間複雜度為 -
O(√n)
示例
以下為程式碼 -
const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;
const blockSearch = (arr = [], target) => {
let { length: len } = arr;
let step = Math.floor(Math.sqrt(len));
let blockStart = 0
let currentStep = step;
while (arr[Math.min(currentStep, len) - 1] < target) {
blockStart = currentStep;
currentStep += step;
if (blockStart >= len)
return -1;
}
while (arr[blockStart] < target){
blockStart++;
if (blockStart == Math.min(currentStep, len))
return -1;
}
if (arr[blockStart] == target)
return blockStart
else
return -1;
};
console.log(blockSearch(arr, target));輸出
以下是控制檯上的輸出 -
10
更新時間： 11-Dec-2020
211 次檢視
廣告