二進制搜索未運行？

Question

我試着在我的代碼示例中使用二分搜索算法，但它沒有像我期望的那樣運行。我不知道爲什麼。請解釋我

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80]; 

function binarySearch (array, numberToSearch) { 
var firstIndex = 0; 
var lastIndex = array.length - 1; 
var currentIndex; 
var currentElement; 

currentIndex = (lastIndex + firstIndex)/2 | 2; 
currentElement = array[currentIndex]; 

while (firstIndex <= lastIndex) { 
    if (numberToSearch === currentElement) { 
     // found 
     console.log(currentIndex); 
     return currentIndex; 
    } else if (numberToSearch < currentElement) { 
     lastIndex = currentIndex - 1; 
     currentIndex = (lastIndex + firstIndex)/2 | 2; 
     currentElement = array[currentIndex]; 
    } else if (numberToSearch > currentElement) { 
     firstIndex = currentIndex + 1; 
     currentIndex = (lastIndex + firstIndex)/2 | 2; 
     currentElement = array[currentIndex]; 
    } 
} 
return -1; 
} 
binarySearch(array, 12); 

我應該打印：5，但沒有happend

Answer 1

什麼是你的代碼錯誤：

1. 應該var currentIndex = (lastIndex + firstIndex)/2 | 0; （不| 2）;

2. currentIndex和currentElement應該在循環內的每個 迭代計算。

所以，這是你的代碼的修正版本：

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80]; 
 

 
function binarySearch (array, numberToSearch) { 
 
var firstIndex = 0; 
 
var lastIndex = array.length - 1; 
 

 
while (firstIndex <= lastIndex) { 
 
    var currentIndex = (lastIndex + firstIndex)/2 | 0; 
 
    var currentElement = array[currentIndex]; 
 
    if (numberToSearch === currentElement) { 
 
     return currentIndex; 
 
    } else if (numberToSearch < currentElement) { 
 
     lastIndex = currentIndex - 1; 
 
    } else if (numberToSearch > currentElement) { 
 
     firstIndex = currentIndex + 1; 
 
    } 
 
} 
 
return -1; 
 
} 
 

 
console.log(binarySearch(array, 99)); // -1 
 
console.log(binarySearch(array, 12)); // 5

順便說一句，這var currentIndex = (lastIndex + firstIndex)/2 | 0;看起來相當不尋常。常見的方式是var currentIndex = Math.floor((lastIndex + firstIndex)/2);

Answer 2

首先，什麼是按位OR這裏的一點：

currentIndex = (lastIndex + firstIndex)/2 | 2; 

我覺得應該是：

currentIndex = (lastIndex + firstIndex)/2; 

有一個在搜索基本缺陷空間更新。 當numberToSearch < currentElement指middle element（位於索引CURRENTINDEX元件）大於將要搜索數目，因此，正確新邊界是：

lastIndex = currentIndex - 1; 

而且當numberToSearch > currentElement指在索引CURRENTINDEX的middle element（元件）小於要搜索的數量，因此，正確的新的邊界是：

firstIndex = currentIndex + 1; 

因此，正確的代碼是：

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80]; 

function binarySearch (array, numberToSearch) { 
var firstIndex = 0; 
var lastIndex = array.length - 1; 
var currentIndex; 
var currentElement; 

currentIndex = (lastIndex + firstIndex)/2; 
currentElement = array[currentIndex]; 

while (firstIndex <= lastIndex) { 
    if (numberToSearch === currentElement) { 
     // found 
     console.log(currentIndex); 
     return currentIndex; 
    } else if (numberToSearch < currentElement) { 
     lastIndex = currentIndex - 1; 
     currentIndex = (lastIndex + firstIndex)/2 | 2; 
     currentElement = array[currentIndex]; 
    } else if (numberToSearch > currentElement) { 
     firstIndex = currentIndex + 1; 
     currentIndex = (lastIndex + firstIndex)/2 | 2; 
     currentElement = array[currentIndex]; 
    } 
} 
return -1; 
} 
binarySearch(array, 12); 

Answer 3

這裏是你的答案更正與所有我更新的地方。你非常接近！看起來好像你在合併二進制搜索的iterative版本和recursive解決方案。

CodePen Demo

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80]; 

function binarySearch (array, numberToSearch) { 
    var firstIndex = 0; 
    var lastIndex = array.length - 1; 
    var currentIndex; 
    var currentElement; 

    while (firstIndex <= lastIndex) { 
    currentIndex = (lastIndex + firstIndex)/2 | 0; //should default to zero, not Two! 
    currentElement = array[currentIndex];//These should both update every iteration so it does not infinitely loop! 
    if (numberToSearch === currentElement) { 
     // found 
     console.log(currentIndex); 
     return currentIndex; 
    }else if (numberToSearch < currentElement) { 
     lastIndex = currentIndex - 1; //If current is too big, move right pointer to the left 
    }else if (numberToSearch > currentElement) { 
     firstIndex = currentIndex + 1;//If current is too small, move left pointer to the right 
    } 
    } 
    return -1;//When condition of while it broken and no solution has been found, return -1 to indicate it is not in the array 
} 
binarySearch(array, 12) //5 

進一步利用Math.floor()作爲number | 0is sometimes faster.