Javascript 刷 LeetCode 學演算法 – 搜尋 Linear Search, Binary Search

Linear Search

時間複雜度：O(n)

744. Find Smallest Letter Greater Than Target

撞到語法不夠熟悉的問題，原本嘗試在 forEach 中 return 和 break，發現不適用
這種情況適合改用 for loop or every 等等其他方法，可參考以下文章

https://masteringjs.io/tutorials/fundamentals/foreach-break

Binary Search

時間複雜度： O log(n)

適用情境：在一個已排序的陣列中，找出其中特定的值

實作關鍵：遞迴or無窮迴圈，雙指標、中值
=> 設立雙指標、中值，並在查找的過程中不斷移動邊界

367. Valid Perfect Square

---

延伸閱讀：

取中值的公式

直觀來說會寫

int mid = (low + high)/2;

但這篇文章提到建議改寫

int mid = low + (high – low)/2;

原因是超過最大正整數時，會溢位，這時候取的中值就會是錯的

But if we calculate the middle index like this means our code is not 100% correct, it contains bugs.

That is, it fails for larger values of int variables low and high. Specifically, it fails if the sum of low and high is greater than the maximum positive int value(2³¹ – 1 ).

The sum overflows to a negative value and the value stays negative when divided by 2.

Reference from geeksforgeeks