在 JavaScript 中，搜尋已排序列表中專案的最佳方法是什麼？

---

在給定的問題陳述中，我們被要求找到使用 JavaScript 功能在已排序列表中搜索元素的最佳方法。當我們談論排序任何列表或陣列時，二分查詢演算法是資料結構中最好的方法。

什麼是 JavaScript 中已排序列表中的二分查詢？

讓我們瞭解 JavaScript 中列表的工作原理。

列表是一個儲存多個元素的物件。在程式設計中，列表是在一個屋簷下收集類似資料元素的集合。由於列表也是一個物件，它具有一些屬性和方法，使在 JavaScript 中使用列表更容易。

以下是 JavaScript 中定義列表的語法：

list = [
    { day: 'Monday', reading: 3, id: 201},
    { day: 'Tuesday', reading: 5, id: 202},
    { day: 'Sunday', reading: 6, id: 405}
];

在資料結構中，二分查詢是在已排序列表中搜索專案的一種非常有效的方法。二分查詢基本上基於分治法。這種方法需要 O(log n) 時間，這比線性搜尋更好，因為線性搜尋演算法需要 O(n) 時間。

二分查詢可以使用迭代和遞迴方法實現。

我們得到了一個已排序的列表。我們的任務是藉助二分查詢找到列表中元素的索引。所以我們將用一個例子來理解這一點

Input array = {2, 4, 6, 8, 10, 12}
        a = 5
Output : Item found!

Input array = {2, 4, 6, 8, 10, 12}
        a = 7
Output : Item not found!

查詢元素的邏輯

在 javascript 中查詢已排序列表中專案的最快捷方法是使用二分查詢演算法。

該演算法基於分治法。因此，在分治法中，我們將已排序的列表分成兩半，並將搜尋元素與中間項進行比較。

如果中間元素與搜尋元素相似，則搜尋任務完成。否則，我們檢查搜尋項是否小於中間元素，則搜尋將繼續在列表的左半部分進行。如果搜尋項大於中間元素，則我們在已排序列表的剩餘右半部分搜尋它。如果中間元素與搜尋元素相似，則搜尋任務完成。否則，我們檢查搜尋項是否小於中間元素，則搜尋將繼續在列表的左半部分進行。如果搜尋項大於中間元素，則我們在已排序列表的剩餘右半部分搜尋它。

演算法

步驟 1 - 宣告一個名為 itemSearch 的函式，該函式接收列表和要搜尋的元素作為引數。

步驟 2 - 宣告左指標和右指標變數以查詢搜尋元素的確切位置。

步驟 3 - 我們在步驟 1 中宣告的函式基本上是一個遞迴函式。該函式在其內部使用 while 迴圈。此迴圈將一直執行，直到左元素小於或等於右元素。

步驟 4 - 接下來，在 while 迴圈之後，我們將透過新增左元素和右元素並將總和除以 2 來計算中間元素。因此，在這個步驟中，我們得到了中間元素。

步驟 5 - 需要對步驟 4 中的特定中間元素遞迴地執行此操作。接下來，我們將檢查搜尋項是否小於或大於中間項。如果它小於搜尋項，則在列表的左側查詢它，否則在中間元素的右側搜尋。

步驟 6 - 現在，為了檢查搜尋項，我們將使用中間變數來檢查中間元素的條件。如果 middleElement 小於搜尋項，則將中間計數增加 1。否則，將中間計數減少 1。

步驟 7 - 這就是遞迴二分查詢的工作方式。現在，在此步驟中，定義一個已排序的列表和搜尋項，並呼叫該函式以獲取輸出。

示例

// define function for binary search
function itemSearch(list, searchItem) {
    let left = 0;
    let right = list.length - 1;

    // loop for finding the element
    while (left <= right) {
      const middle = Math.floor((left + right) / 2);
      const middleElement = list[middle];
       
      // condition for search item
      if (middleElement === searchItem) {
        return middle;
      } else if (middleElement < searchItem) {
        left = middle + 1;
      } else {
        right = middle - 1;
      }
    }
 
    return -1;
  }

  // create search list
  const searchList = [11, 13, 15, 17, 19];
  const searchingFor = 15;
 
  // calling the function
  const foundIndex = itemSearch(searchList, searchingFor);
 
  // condition for found or not found
  if (foundIndex === -1) {
    console.log("Element has not found.");
  } else {
    console.log(`Element found at index ${foundIndex}.`);
  }

輸出

 Element fFound at index 2.

上述程式碼是在檢視問題陳述時人們可以想到的非常簡單的程式碼，但是理解了這個邏輯之後，您可以透過使其更靈活和更簡單來最佳化其空間和時間質量。

在上面的程式碼中，我們聲明瞭一個函式，該函式接收列表和搜尋項作為輸入。然後我們一步一步地進行，首先透過獲取中間元素將列表分成兩半。並透過比較來搜尋所需的元素。

在程式碼中，itemSearch 函式用於在已排序列表 [11, 13, 15, 17, 19] 中搜索數字。該函式返回 15 的索引值 2。這表明搜尋項在索引 2 處找到。

時間複雜度

因此，已排序列表的長度為 n，這決定了二分查詢演算法的時間複雜度，它將為 O(log n)。這是因為搜尋空間的大小在每次迴圈迭代中都會減半。作為輸出，查詢專案所需的搜尋次數等於列表的大小。

除了輸入列表的大小外，此技術還需要恆定的記憶體。因此，此方法的空間複雜度為 O(1)。因為演算法可以透過僅儲存少量變數來跟蹤當前搜尋空間和搜尋元素的位置。

結論

這就是我們解決上述問題陳述的方法。在 JavaScript 中搜索已排序列表中元素的最簡單可靠的方法是使用二分查詢演算法。此方法的時間複雜度為 O(log n)，空間複雜度為 O(1)。該方法不斷將已排序列表分成兩半，並將搜尋項與中間元素進行比較。並允許它快速縮小搜尋記憶體，直到找到搜尋項不在列表中。