> For the complete documentation index, see [llms.txt](https://ret2basic.gitbook.io/ctfnote/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ret2basic.gitbook.io/ctfnote/computer-science/data-structures-and-algorithms/binary-search.md).

# Binary Search

## **Binary Search (LeetCode 704)**

{% embed url="<https://leetcode-cn.com/problems/binary-search>" %}
LeetCode 704
{% endembed %}

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with $$O(\log n)$$ runtime complexity.

**Example 1:**

```
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
```

**Example 2:**

```
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1  
```

**Constraints:**

* `1 <= nums.length <= 10**4`
* `-10**4 < nums[i], target < 10**4`
* All the integers in nums are unique.
* `nums` is sorted in ascending order.

**Solution:**

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1

        while low <= high:
            mid = (low + high) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] <= target:
                low = mid + 1
            else:
                high = mid -1
            
        return -1
```

## **Template**

* The searching space is always a closed interval: `[low, high]`.
* Loop condition is always `while low <= high`.
* The return value is always `mid`.
* Always use `low = mid + 1` and `high = mid - 1`.
* If `nums[mid]` have repeated values in `nums`, determine its position according to `nums[mid - 1]` and `nums[mid + 1]`.
* Handle the "hit" case first. For example, handle `if nums[mid] == target` first, then `elif nums[mid] < target`, then `else`.

## **Find First and Last Position of Element in Sorted Array (LeetCode 34)**

{% embed url="<https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array>" %}
LeetCode 34
{% endembed %}

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return `[-1, -1]`.

You must write an algorithm with $$O(\log n)$$ runtime complexity.

**Example 1:**

```
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
```

**Example 2:**

```
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
```

**Example 3:**

```
Input: nums = [], target = 0
Output: [-1,-1]
```

**Constraints:**

* `0 <= nums.length <= 105`
* `-109 <= nums[i] <= 109`
* `nums` is a non-decreasing array.
* `-109 <= target <= 109`

**Solution:**

```python
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def search_first():
            low, high = 0, len(nums) - 1

            while low <= high:
                mid = (low + high) // 2

                # If hit
                if nums[mid] == target:
                    if mid == 0 or nums[mid - 1] != target:
                        return mid
                    # If nums[mid] is not the first occurrence,
                    # search the lower interval
                    else:
                        high = mid - 1
                elif nums[mid] > target:
                    high = mid - 1
                else:
                    low = mid + 1
            
            return -1
        
        def search_last():
            low, high = 0, len(nums) - 1

            while low <= high:
                mid = (low + high) // 2

                # If hit
                if nums[mid] == target:
                    if mid == len(nums) - 1 or nums[mid + 1] != target:
                        return mid
                    # If nums[mid] is not the last occurrence,
                    # search the higher interval
                    else:
                        low = mid + 1
                elif nums[mid] > target:
                    high = mid - 1
                else:
                    low = mid + 1
                
            return -1

        first = search_first()
        last = search_last()
        return [first, last]

        
```

## **Find Smallest Letter Greater Than Target (LeetCode 744)**

{% embed url="<https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target>" %}
LeetCode 744
{% endembed %}

Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target.

Note that the letters wrap around.

For example, if `target == 'z'` and `letters == ['a', 'b']`, the answer is `'a'`. &#x20;

**Example 1:**

```
Input: letters = ["c","f","j"], target = "a"
Output: "c"
```

**Example 2:**

```
Input: letters = ["c","f","j"], target = "c"
Output: "f"
```

**Example 3:**

```
Input: letters = ["c","f","j"], target = "d"
Output: "f"
```

**Constraints:**

* `2 <= letters.length <= 10**4`
* `letters[i]` is a lowercase English letter.
* `letters` is sorted in non-decreasing order.
* `letters` contains at least two different characters.
* `target` is a lowercase English letter.

**Solution:**

```python
class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        low, high = 0, len(letters) - 1

        while low <= high:
            mid = (low + high) // 2

            # If hit
            if letters[mid] > target:
                if mid == 0 or letters[mid - 1] <= target:
                    return letters[mid]
                else:
                    high = mid - 1
            else:
                low = mid + 1
        
        return letters[0]

```