---
tags: DSA in JavaScript
---
# Ch.10 Searching Algorithm
> 本篇只著重於陣列搜尋

搜尋：尋找陣列內符合條件元素，並回傳第一個符合的結果，若都沒有符合，則回傳 -1

常見的搜尋方法：
1. Linear Search
2. Binary Search

## Linear Search
- 在陣列中使用迴圈一個個比對元素
- 在 JavaScript 中，有關陣列搜尋的方法背後都是 linear search
- indexOf
- includes
- find
- findIndex
- lastIndexOf
- 時間複雜度為 O(n)

## Binary Search
- 前置作業：大小依序排列整齊的陣列
- 大致流程如下
1. 新增三個變數，分別代表陣列的開頭 (`0`)、結尾 (`array.length - 1`) 與中間位置 (`array.length / 2`)
4. 若中間值正好符合目標值，回傳結果
5. 若中間值大於目標值，代表目標值範圍在開頭與中間值之間，因此將結尾位置改為中間值，中間值重新計算 (`(開頭 + 結尾) / 2`)
6. 若中間值小於目標值，代表範圍在中間值與結尾之間，重新計算開頭與中間值的位置
7. 回到 `3` 重複 `3`、`4`、`5` ，直到回傳結果，或是開頭大於結尾，代表陣列中沒有目標值，回傳 -1

- 時間複雜度： O(log n)

## 優劣比較

| | Linear | Binary |
| ----- | ---------------------------- | -------------------------- |
| pros. | 使用方便、直觀、不須前置作業 | 大幅減少處理時間、加快速度，可以應付更多更大的陣列 |
| cons. | 若是大型陣列 (10 萬以上)，則會大幅增加處理時間 | 需要將陣列事先排序整齊 |