# 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]

```


---

# 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://ret2basic.gitbook.io/ctfnote/computer-science/data-structures-and-algorithms/binary-search.md?ask=<question>
```

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.