Binary Search

✅ Binary Search

search algorithm
used on sorted array
repeatedly divide search interval into two parts(binary) and search

1. Sort
   
2. set left, right, mid
   
3. While left < right
   
4. Compare mid and serach value
   
5. If mid == search value, search terminates
   
   • If mid < search value, search right
     
   • If mid > search value, search left
     

⭐️ Keyword

✅ Code

https://soheeparklee.github.io/posts/CT-1-51/

✅ Time complexity

O(log N) search interval is halved in each step

✅ Space complexity

O(1)

👍🏻 Pros

• do not have to search all the array, just search half

👎🏻 Cons

• array has to be sorted

💡 Reference