[DSA][Binary Search] 01. Binary Search

LeetCode 704

 

01. 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.

 

 

[질문하기]

- 배열의 길이의 제한이 어떻게 되나요? (l+r이 오버플로우를 일으킬 수 있는지)

- 배열에 중복된 값이 있을 수 있나요? NO

 

 

[아이디어]

- Binary Search를 사용하자.

 

 

[풀이 1] Binary Search

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            # (l + r) // 2 can lead to overflow
            mid = l + ((r - l) // 2)  
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        
        return -1

주어진 배열은 이미 오름차순으로 정렬되어 있기 때문에, 이진 탐색(Binary Search) 알고리즘을 사용하면 target 값을 효율적으로 찾을 수 있다.

 

한 가지 고려하면 좋은 점은, mid를 구할 때 (l + r) / 2 대신 l + (r - l) / 2로 구하는 것이 안전하다는 것이다.

배열의 인덱스를 나타내는 l과 r을 더한 값이 32비트 정수(int) 타입의 최댓값을 초과할 수 있기 때문에, 이를 방지하려면 l과 r의 합을 더하는 대신 후자의 방법으로 중간값을 계산하는 것이 좋다.

 

 

⏱️ 시간복잡도

매 탐색마다 배열의 후보 범위가 절반씩 줄어들기 때문에 O(logn)의 시간 복잡도를 가진다.

🧠 공간복잡도

추가적인 공간 없이 변수만 사용하기 때문에 O(1)의 공간 복잡도를 갖는다.