如何使用遞歸創建二進制搜索

Question

我正在嘗試編寫一個我從未做過的「二分查找」。當搜索的值是6或2時，下面的代碼不起作用，我想知道我在做什麼錯誤以及如何解決它。

編輯

爲了解釋什麼是該做的（根據我的理解）的二進制搜索需要一個數組已經排序，它然後尋找一個數組的中點指數。例如，如果陣列有九個索引（0-8）的中點。將指數4.

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; 

該算法然後確定是否該中點具有比要搜索的數目更高或更低的值對於。數組一側的所有元素不包含搜索到的數字，並且只存在於中點值之前。如果值搜索是8，那麼結果將是：

[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] 
array midpoint value: 5 
[ 5, 6, 7, 8, 9 ] 
array midpoint value: 7 
[ 7, 8, 9 ] 
array midpoint value: 8 

代碼

//_________________________________________________BEGIN notes 

    // Step 1. Get length of array 
    // Step 2. Find mid point 
    // Step 3. Compare if mid point is lower or higher than searched number 
    // Step 4. lop off unneeded side 
    // Step 5. go to step 1 
//_________________________________________________END notes 

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55]; 

function getMidPoint(arr, searchNumb) { 
    var length = arr.length; 
    var midPoint = Math.floor(length/2); 
    var newArr = arr; 
    console.log(arr); 
    console.log("array midpoint value: " + arr[midPoint]); 

    if (arr[midPoint] > searchNumb) { 

     var newArr = arr.slice(0, arr[midPoint]); 
     return getMidPoint(newArr, searchNumb); 

    } else if (arr[midPoint] < searchNumb) { 

     var newArr = arr.slice(midPoint, arr.length); 
     return getMidPoint(newArr, searchNumb); 

    } else { 
     return arr 
    } 
} 

Answer 1

1. 你正在切錯了。

使用此代碼：

//_________________________________________________BEGIN notes 

    // Step 1. Get length of array 
    // Step 2. Find mid point 
    // Step 3. Compare if mid point is lower or higher than searched number 
    // Step 4. lop off unneeded side 
    // Step 5. go to step 1 
//_________________________________________________END notes 

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55]; 

function getMidPoint(arr, searchNumb) { 
    var length = arr.length; 
    var midPoint = Math.floor(length/2); 
    var newArr = arr; 
    console.log(arr); 
    console.log("array midpoint value: " + arr[midPoint]); 

    if (arr[midPoint] > searchNumb) { 

     var newArr = arr.slice(0, midPoint); 
     return getMidPoint(newArr, searchNumb); 

    } else if (arr[midPoint] < searchNumb) { 

     var newArr = arr.slice(midPoint + 1, arr.length); 
     return getMidPoint(newArr, searchNumb); 

    } else { 
     return midPoint; 
    } 
} 

此外，如果搜索元素不在陣列，這將無限繼續。爲此也添加一個基本案例。

Answer 2

我覺得這條線：

var newArr = arr.slice(0, arr[midPoint]); 

也許應該是：

var newArr = arr.slice(0, midPoint); 

但我不知道這是否是您的代碼唯一的問題。 （我不清楚代碼實際上應該做什麼，現在「getMidPoint」似乎返回一個包含搜索值的較小數組。）

Answer 3

有您的代碼2個問題： -

1）你是不正確的切片它 2）您沒有把任何基礎條件

此代碼應該有希望的工作： -

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55]; 

function getMidPoint(arr, searchNumb) { 
    var length = arr.length; 
    var midPoint = Math.floor(length/2); 
    var newArr = arr; 
    console.log(arr); 
    console.log("array midpoint value: " + arr[midPoint]); 

    if (arr[midPoint] > searchNumb) { 

     var newArr = arr.slice(0, midPoint); 
     return getMidPoint(newArr, searchNumb); 

    } else if (arr[midPoint] < searchNumb) { 

     var newArr = arr.slice(midPoint+1, arr.length); 
     return getMidPoint(newArr, searchNumb); 

    } else { 
     return arr[midPoint]; 
    } 
} 

如果在數組中找不到元素，則此函數將返回undefined。

Answer 4

語言不可知，下面是遞歸二分法搜索實現的簡化流程，假設我們有一個（最初是非空的）數組[ARR]和一個目標[T]，我們將ARR的中間元素稱爲M：

// 1. If M == T, return true 
// 2. If length of ARR is 0, return false (note: step 1 short circuits, ensuring we only hit step 2 if step 1 evaluates to false) 
// 3. If T < M, return the result of the recursion on the lower half of ARR 
// 4. If T > M, return the result of the recursion on the the latter half of ARR 

以下是執行上述控制流程的解決方案。這類似於在這個崗位已經提出的解決方案，有幾個值得注意的區別：

function binarySearch(arr, target, start=0, stop=(arr.length-1)) { 

    let midPoint = Math.floor(((stop-start)/2) + start) 

    switch (true) { 
    case arr[midPoint] === target: 
     return true 
    case stop - start === 0: 
     return false 
    case arr[midPoint] < target: 
     return binarySearch(arr, target, midPoint+1, stop) 
    case arr[midPoint] > target: 
     return binarySearch(arr, target, start, midPoint) 
    } 
} 

讓我們來解開這個實現的主要區別：不再使用

• 片：

  我們不想使用Array.prototype.slice，因爲它是一個相對昂貴的操作（用每次遞歸調用複製當前數組的一半！），並且算法不需要函數正確地。

  代替切片，我們將通過縮小搜索範圍的數組範圍的開始和停止索引傳遞給。這可以讓我們的堆幸福，因爲它不會與同一個（可能是巨大的）數組的（可能很多）部分，永久性副本混淆。

• 我們傳遞兩個額外的參數，並且他們有默認值：

  這些參數（啓動和停止）服務來跟蹤我們目前經常性的陣列的範圍。他們是我們的替代品！ 默認參數使我們能夠調用這個遞歸函數，就像我們在使用slice時一樣（當用戶第一次調用時不應該提供明確的範圍）。

• 我們使用switch語句：

  switch語句與一個的if-else鏈的速度取決於幾個因素，最引人注目的是編程語言，並在每個條件語句的數量。這裏使用的switch語句主要是爲了可讀性。這是一個控制流程，它匹配我們在這個遞歸函數中處理的事情：4個離散情況，每個情況都需要不同的操作。此外，少數人對if-else語句有超過3次邏輯測試的罕見過敏。 關於JavaScript的switch語句，其性能與if-else語句，請看看這篇文章的詳細信息：Javascript switch vs. if...else if...else，可鏈接到這個更多的信息頁面http://archive.oreilly.com/pub/a/server-administration/excerpts/even-faster-websites/writing-efficient-javascript.html