Binary Search

• 首先，重點是要先排序好，才能進行Binary Search
• 每次切一個區間，比中間大就找右邊，比中間小就找左邊，持續至找到

• Code
  

  **Quiz:要怎麼算中間值：

  1. mid = (left + right)/2
     優：運算速度快（較2少了一次運算）
     缺：若left跟right兩個值皆大，則可能會overflow
  2. mid = left + (right - left)/2
     優：不會overflow
     缺：運算速度慢**

  寫recursive壞處：
  1.沒效率
  2.Stack overflow
  3.很難debug

• Extension
  1.Other similar problems
  Interval finding
  Non-zero elements finding
  2.Binary Search using Multiple Key s
  Stable sort：排序前兩個值一樣，排序後不會改變順序
  從最後的key往前排序 --> start from the least-significant key
  Preprocessing時要用stable sorting，由後往前排序（用LSK）
  Search時用MSK