# Binary Search
Source: [LeetCode: Introduction to Binary Search](https://leetcode.com/articles/introduction-to-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.
## **3 Templates for 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:**
```java
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:**
```java
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:**
```java
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`
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://aaronice.gitbook.io/lintcode/binary-search.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.