Binary Search

Binary Search (LeetCode 704)

力扣

LeetCode 704

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:

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)

力扣

LeetCode 34

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:

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)

力扣

LeetCode 744

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:

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]