0704. Binary Search

Easy | Array + Binary Search | 228 ms (91.88%), 15.5 MB (68.27%)

❓ Problem Statement

Source: LeetCode - Binary Search GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

💡 Ideas

Standard Binary Search Problem.

Boundary / Search Space

Left (Minimum) = 0 Right (Maximum) = len(array) (last element could be the answer)

Condition

While Loop = Left < Right Return = array[mid] == target number

Return Value

Index or -1 (not found)

🤖 Python3

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # (base case)
        if len(nums) == 1: return 0 if nums[0] == target else -1
        
        # ==================================================
        #  Array + Binary Search                           =
        # ==================================================
        # time  : O(log(n))
        # space : O(1)

        l, r = 0, len(nums)
        while l < r:
            mid = (l + r) // 2
            
            if nums[mid] == target: return mid
            elif nums[mid] > target: r = mid
            elif nums[mid] < target: l = mid + 1
                
        return -1

🤖 Java