Comment on page

# Binary Search

Binary Search should be considered every time you need to search for an index or element in a collection. If the collection is unordered, we can always sort it first before applying Binary Search.
Template 1 and 3 are the most commonly used and almost all binary search problems can be easily implemented in one of them. Template 2 is a bit more advanced and used for certain types of problems.

### Template #1:

int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while (left <= right) {
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// End Condition: left > right
return -1;
}
Distinguishing Syntax:
• Initial Condition:`left = 0, right = length-1`
• Termination:`left > right`
• Searching Left:`right = mid-1`
• Searching Right:`left = mid+1`

### Template #2:

int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length;
while (left < right) {
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
// Post-processing:
// End Condition: left == right
if (left != nums.length && nums[left] == target) return left;
return -1;
}
It is used to search for an element or condition which requires accessing the current index and its immediate right neighbor's index in the array.
Key Attributes:
• An advanced way to implement Binary Search.
• Search Condition needs to access element's immediate right neighbor
• Use element's right neighbor to determine if condition is met and decide whether to go left or right
• Guarantees Search Space is at least 2 in size at each step
• Post-processing required. Loop/Recursion ends when you have 1 element left. Need to assess if the remaining element meets the condition.
Distinguishing Syntax:
• Initial Condition:`left = 0, right = length`
• Termination:`left == right`
• Searching Left:`right = mid`
• Searching Right:`left = mid+1`

### Template #3:

int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while (left + 1 < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
// Post-processing:
// End Condition: left + 1 == right
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
It is used to search for an element or condition which requires _accessing the current index and its immediate left and right neighbor's index _in the array.
Key Attributes:
• An alternative way to implement Binary Search
• Search Condition needs to access element's immediate left and right neighbors
• Use element's neighbors to determine if condition is met and decide whether to go left or right
• Gurantees Search Space is at least 3 in size at each step
• Post-processing required. Loop/Recursion ends when you have 2 elements left. Need to assess if the remaining elements meet the condition.
Distinguishing Syntax:
• Initial Condition: `left = 0, right = length-1`
• Termination: `left + 1 == right`
• Searching Left: `right = mid`
• Searching Right: `left = mid`