Binary Search 二元搜尋法

tags: LeetCode

二元搜尋法，也就是將排序好的資料分割成兩等份。每次挑出一個數字，和中間值比較，判斷目標在前半或後半。然後再進行二元分割。它的時間複雜度是

$O(logn)$。

---

一、步驟觀察

• 找出中間值
• 如果目標值 === 中間值，則傳回 index
• 如果目標值 > 中間值，則從右邊子陣列找，重複步驟一 (recur for the right half)
• 如果目標值 < 中間值，則從左邊子陣列找，重複步驟一 (recur for the left half)

( 圖片來源 wiki )

二、實際操作

使用哪種資料結構：Array

• x 為目標
• 將 left l 和 right r 作為陣列兩端的索引值
• 如果 r > l，可以二分的情況
  • 將 x 與中間位置 middle 的值做比較
    • 如果 x > arr[middle]，呼叫 binarySearch() 處理右邊陣列
    • 如果 x < arr[middle]，呼叫 binarySearch() 處理左邊陣列
    • 如果 x === arr[middle]，回傳 middle
• 回傳 -1，代表沒有相對應的值

邏輯：

  arr <- an array of integers
  let len be the length of arr
  let l be the beginning index of array
  let r be the end index of the array
  
  func binarySearch(arr, l, r, x)
    if r > l then
      middle = l+(r+l)/2
      if x > middle then
        return binarySearch(arr , middle+1, r, x)
      end if
      if x < middle then
        return binarySearch(arr, l, middle-1, x)
      end if
      if x === middle then
        return middle
      end if
    end if
    return -1    
  end func

程式碼實作：

debugger
function binarySearch(arr, l, r, x) {

  if (r > l) {
    let mid = l + Math.floor((r-l)/2)
    
    if (x > arr[mid]) return binarySearch(arr, mid+1, r, x)
    
    if (x < arr[mid]) return binarySearch(arr, l, mid-1, x)
    
    if (x === arr[mid]) return mid
  }
  
  return -1
  
}

let arrayData = [1, 4, 6, 23, 45, 65, 68, 77, 89, 90, 93, 103]

let result = binarySearch(arrayData, 0, arrayData.length-1, 93)

console.log(result)

三、時間複雜度 Big O

資料來源

• Binary Search