[LeetCode | Python] 704. Binary Search

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.

간단한 바이너리서치(이진탐색) 문제!

이진탐색은 정렬된 배열에서만 사용할 수 있는 탐색 알고리즘이다. 

이진탐색은 매번 탐색 범위를 절반으로 줄이므로 시간복잡도가 O(n)이다.

또한 문제에서 명시적으로 O(log n) 시간 복잡도로 해결하라고 요구하고 있는데,

O(log n) 복잡도를 가지는 대표적인 알고리즘은 이진 탐색이다!

 

풀이: 이진탐색

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
        l = 0
        r = len(nums) - 1
        
        while l <= r:
            
            mid = (l + r) // 2
            
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        
        return -1