> 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="" %} 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="" %} 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="" %} 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'`. **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 This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## 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, and the optional `goal` query parameter: ``` GET https://ret2basic.gitbook.io/ctfnote/computer-science/data-structures-and-algorithms/binary-search.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. 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.