https://www.greatfrontend.com/questions/javascript/binary-search
Implement a function that performs binary search on an array of numbers. The function should take in a sorted array of integers and a target integer to find. It returns the index of the target element or -1, if the target element doesn’t exist in the array.
Examples
binarySearch([1, 2, 3, 6, 9, 11], 6); // 3
binarySearch([1, 2, 3, 12, 16, 14], 5); // -1這題就是用二分搜尋法找出目標的值在陣列中的索引。
二分搜尋法
首先要先知道二分搜尋法是怎麼樣進行搜索的：
- 找出當前陣列的中位數(
陣列長度/2)，若陣列長度為奇數則除以2後無條件捨去或進位都可以。比方說長度為 5，那麼中位數可以是第 2 或第 3 個數。 - 比較目標值與中位數的大小，若
目標值 > 中位數，則代表目標值在中位數右側，反之目標值則在左側。判斷出目標值在左側還是右側後，將目標值(含)另一側的數全部捨棄不看。 - 剩餘的數再重複執行以上兩個步驟直至找到目標數或者找完所有數（可能找不到目標值）。
以範例的輸入為例，要在 [1, 2, 3, 6, 9, 11] 中找到 6 的索引，使用二分搜尋法的過程即為：
-0--1--2--3--4---5-
[1, 2, 3, 6, 9, 11] => 找到中位數 3，6 比 3 大所以捨棄中位數(含)左半邊的數
-3--4---5-
[6, 9, 11] => 找到中位數 9，6 比 9 小所以捨棄中位數(含)右邊的數
-3-
[6] => 找到中位數 0，6 為目標值，輸出索引 3Solution
- 循環終止條件設為
startIndex <= endIndex，只要 startIndex 小於等於 endIndex 就繼續，如果找不到目標值的話最終 startIndex 會大於 endIndex - 獲取中位數索引的方式：
Math.floor((endIndex + startIndex) / 2) endIndex = midIndex - 1;和startIndex = midIndex + 1;這邊中位數 +1, -1 是為了下一輪比較時不重複判斷中位數，如果中位數是要找的值的話會符合的是第一個判斷式if (arr[midIndex] === target)
export default function binarySearch(arr, target) {
let startIndex = 0;
let endIndex = arr.length - 1;
while (startIndex <= endIndex) {
let midIndex = Math.floor((endIndex + startIndex) / 2);
if (arr[midIndex] === target) {
return midIndex;
} else if (arr[midIndex] > target) {
endIndex = midIndex - 1;
} else {
startIndex = midIndex + 1;
}
}
return -1;
}
