Binary Search

Binary Search

  • Given a sorted array, find any/first/last element in the array

  • Time complexity T(n) = T(n/2) + O(1) = T(n/4) + O(1) + O(1) = T(n/8) + O(1) + O(1) + O(1) = ….. = O(logn)

  • use while loop

  • What’s the condition in while loop? start + 1 < end (vary important)

  • How to calculate mid point? mid = start + Math.floor((end - start)/2);