# Binary Search

Source: [LeetCode: Introduction to Binary Search](https://leetcode.com/articles/introduction-to-binary-search/)

<https://leetcode.com/explore/learn/card/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**

![](https://1611446478-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M63nDeIUEfibnkE8C6W%2Fsync%2F3c107decd2cc6bb677fee2227e986d5306f3d73c.png?generation=1588144784448320\&alt=media)

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`