資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法學研究JavaScript程式：在已排序並旋轉的陣列中搜索元素
當陣列按升序排序然後透過某個樞軸點旋轉後，使用傳統的搜尋演算法查詢元素就變得具有挑戰性。作為開發者，您需要找到一個有效的解決方案來解決這個問題。
在本文中，我們將指導您完成編寫JavaScript程式以在已排序並旋轉的陣列中搜索元素的過程。我們將解釋其背後的邏輯，並提供一個逐步實施此程式的方法。
問題陳述
在我們開始之前，讓我們瞭解一下問題陳述。我們有一個已排序的陣列，它已被旋轉了未知的量。
例如，原始陣列可能是[1, 2, 3, 4, 5, 6]，但旋轉後，它變成了[4, 5, 6, 1, 2, 3]。現在，我們需要在旋轉後的陣列中搜索特定元素。
我們需要做的第一件事是找到樞軸點，即陣列旋轉的點。一旦找到樞軸點，我們就可以對兩個子陣列執行二分查詢以找到我們正在尋找的元素。
查詢樞軸點
為了找到樞軸點，我們可以使用改進的二分查詢演算法。我們首先找到陣列的中間元素，並將其與第一個元素進行比較。如果中間元素大於第一個元素，我們就知道樞軸點在陣列的後半部分。如果中間元素小於第一個元素，我們就知道樞軸點在陣列的前半部分。
我們繼續此過程，直到找到樞軸點。一旦找到樞軸點，我們就可以將陣列分成兩個子陣列，並在兩者上執行二分查詢。
輸入
Array: [4, 5, 6, 1, 2, 3]
輸出
Pivot index: 2
請注意，樞軸索引可能因輸入陣列而異。
示例
查詢樞軸點。
在下面的JavaScript程式中，我們有一個已排序並旋轉的陣列[4, 5, 6, 1, 2, 3]。我們使用陣列、起始索引“0”和結束索引“arr.length - 1”呼叫“findPivot”函式。該函式返回樞軸點的索引，在本例中為“2”。
function findPivot(arr, low, high) {
if (high < low) return -1;
if (high === low) return low;
const mid = Math.floor((low + high) / 2);
if (mid < high && arr[mid] > arr[mid + 1]) {
return mid;
}
if (mid > low && arr[mid] < arr[mid - 1]) {
return mid - 1;
}
if (arr[low] >= arr[mid]) {
return findPivot(arr, low, mid - 1);
}
return findPivot(arr, mid + 1, high);
}
// Example usage
const arr = [4, 5, 6, 1, 2, 3];
console.log("Array: " + JSON.stringify(arr));
const pivotIndex = findPivot(arr, 0, arr.length - 1);
console.log("Pivot index:", pivotIndex);
執行二分查詢
一旦找到樞軸點，我們就可以對兩個子陣列執行二分查詢以找到我們正在尋找的元素。我們需要兩個獨立的二分查詢函式：一個用於第一個子陣列，另一個用於第二個子陣列。
輸入 − const arr = [1, 2, 3, 4, 5, 6, 7]; const key = 4;
輸出 − 3
在這個例子中，二分查詢函式返回索引'3'，它對應於陣列中的值'4'。
示例：二分查詢函式
下面的程式使用二分查詢演算法在陣列中搜索鍵。它首先透過比較起始和結束索引來檢查鍵是否在陣列中。如果鍵不存在，則返回-1。如果存在，則計算中間索引並將該索引處的數值與鍵進行比較。如果值等於鍵，則返回中間索引。如果值小於鍵，則繼續在陣列的右半部分搜尋；如果值大於鍵，則在陣列的左半部分搜尋，直到找到鍵或鍵不存在於陣列中。
function binarySearch(arr, low, high, key) {
if (high < low) return -1;
const mid = Math.floor((low + high) / 2);
if (arr[mid] === key) {
return mid;
} else if (key < arr[mid]) {
return binarySearch(arr, low, mid - 1, key);
} else {
return binarySearch(arr, mid + 1, high, key);
}
}
const arr = [1, 2, 3, 4, 5, 6, 7];
const key = 4;
const result = binarySearch(arr, 0, arr.length - 1, key);
console.log("The searched element found at index ", result);
結論
可以使用改進的二分查詢演算法在已排序並旋轉的陣列中搜索元素。此演算法的關鍵是在陣列中識別樞軸點，然後將陣列分成兩個已排序的子陣列。然後對適當的子陣列執行二分查詢以找到鍵。此演算法在JavaScript中的實現需要仔細考慮極端情況和實現細節，但結果是一個快速有效的搜尋函式，可以處理任何大小的已排序和旋轉的陣列。
302 次瀏覽
