<aside> 📌 Binary Search 基本步骤:

• 模型：一段区间里（给个array，一般是sorted），找一个数（target）
• 算法原则：
• Binary Search 基本准则：
• 解题顺序：
• 做题小技巧Summary:
• Typical Problem: </aside>

<aside> 📌 易错点：

• [ ] 逻辑不要想的太麻烦。重点要问自己：array[mid] 跟 reference值相比 (target/neighbor/boundary) 判断什么时候解肯定在这区间里 or 解肯定不在这区间里。按这逻辑去决定 search to left or right; 中点是否确定不是解，可以排除。
• [ ] Incorrect while loop terminating condition - 懒人方法：不清楚就用 left < right - 1之后 post processing ⇒ 错不了。
• [ ] 在 while loop里，找到想要的值，不能直接 return 的话，就 break。i.e. find first and last position of elements
• [ ] Mix with iterating method(brute force) while using binary search ⇒ TC=O(n), not O(logn). i.e. totalOccurence - found first occurence using binary search but iterate to count how many.

Rotated Sorted Array 题:

• [ ] Corner case 要考虑rotate n次回到原来sorted array sequence的情况
• [ ] Duplicates？最左边，最右边跟mid一样？array[mid]跟target一样但是找第一个occurence？
• [ ] Edge cases - Search in Shifted Sorted Array II

In Two Sorted Arrays题：

• [ ] 母题： kth smallest element in two sorted array
• [ ] 解题思路没想到：在两个array里各取 第k/2个元素，对比之后，把小的k/2个元素从search space里移除。没轮删除 k/2个元素。重点：别忘了reduce k (k -= k/2)
• [ ] calculate index from other length(s) or indices. when to + 1 and -1 ? i.e. median of two sorted array
• [ ] 收缩search space时候别忘了update k value ⇒ k -= k/2.
• [ ] 要考虑的很多corner case，包括
  • k == 1
  • 其中array为空
  • 找到k smallest的时候，其中一个array遍历到头，aleft/bleft出界的情况 </aside>

<aside> ✍️ 代码优化建议：

• helper function 可以让代码干净易懂很多 i.e. find first/last position of elements, search in bitonic array
• Use a tenary operator to determin the return value based on wheather the target was found or not. </aside>

<aside> 🌵 Table of Contents

</aside>

Classic

Date: June 24, 2023

Problem : Classic Binary Search

Date: June 24, 2023

Problem : Closest In Sorted Array

Date: June 29, 2023

Problem: Search In Unknown Sized Sorted Array

Date: July 6, 2023

Problem: Koko Eating Bananas

Occurence