Introduction

If sorted data set => binary tree

1. Define search space
   • sorted
   • set left and right ptr
2. Narrowing the search space
   • move ptr inward until only one element remains
   • moves are based on the value @ mid point (1/2 of search space)
   • if the searched value is on the right of mid, move left ptr to the right (resp right ptr to the left)
     1. left = mid+1 if value @ mid cannot be the searched value (resp. right = mid-1)
     2. left = mid if value @ mid could be the searched value (resp. right = mid)
   • mid = left + (right-left)//2 (avoid overflow)
3. Choose an exit condition for the while loop
   • while left < right ends when left = right (right=left=searched value)
   • while left <= right ends when left > right (left surpassed right)
4. Return the correct value
   • return either value @ left or right

Checklist

• 1 - Sorted search space
• 2 - Narrowing search space
• 3 - Choose an exit condition for the while loop
• 4 - Return the correct value