Binary Search

• Maintain low(inclusive) and high(exclusive) range
• low<=goal<high
• Goal = index of value we want
  • If its in the array
  • if not, will have low = hi

Code

1st

low = 0;
high = array.length;
while (low < high){
     int mid = low + (high-low)/2;
     if (mid == target) {return true;}
     if (mid < target) {low = mid+1;}
     if (mid > target) {high = mid;}
}
return false;

2nd

low = 0;
high = array.length-1;
while (low < high){
     int mid = low + (high-low)/2;
     if (mid == target) {return true;}
     if (mid < target) {low = mid+1;}
     if (mid > target) {high = mid-1;}
}
return false;