# Binary Search 二元搜尋法
###### tags: `LeetCode`

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

{%youtube T2sFYY-fT5o %}

## 一、步驟觀察
* 找出中間值
* 如果目標值 === 中間值，則傳回 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](https://www.geeksforgeeks.org/binary-search/)