# Binary Search

Binary Search should be considered every time you need tosearchfor anindexorelementin a collection. If the collection isunordered, we can alwayssortit 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.

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`

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`

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`

Last modified 2yr ago