03.md

Binary Search

Definition

在已排序 (Sorted) array 裡尋找資料是否符合目標值。 並且每次將 array 切分一半，左邊比目標值小，右邊比目標值大，比較中間值與目標值，循序的尋找到目標值。

• 停止條件：找到目標值或走訪完全部元素而沒有找到目標值
• 回傳：若有目標值則回傳 index, 若無則回傳 -1

Performance

• Worst Case: O(logn)
• Best Case: O(1)
• Average Case: O(logn)

Code:

function binarySearch(arr, n) {
  let min = 0;
  let max = arr.length - 1;
  while(min <= max) {
    let middle = Math.floor((max + min) / 2); // 切一半
    if (n > arr[middle]) { // n 在右邊
      min = middle + 1;
    }
    if (n < arr[middle]) { // n 在左邊
      max = middle - 1;
    }
    return middle; // 找到了
  }
  return -1; // 找不到
}