[leetcode] 704. Binary Search - Python

🔍 Problem

https://leetcode.com/problems/binary-search/

---

📰 문제풀이

• 제한 시간: 15분
• 성공 여부: 성공

---

📃 Solving Process

1. 정렬된 데이터에서 주어진 target이 있으면, 해당 자리의 인덱스를 반환해야 한다.
2. 시작 범위는 1 <= nums.length <= 104여서 start = 0, end = len(nums) - 1이다.
3. 계속해서 middle 값과 target 값의 관계를 확인해 탐색 범위를 좁혀준다.
4. 정렬된 모든 범위를 탐색해도 target 값을 찾지 못하면 -1을 반환한다.

---

💻 Code

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

---

⏱ Time Complexity

• 탐색의 범위가 항상 절반씩 줄어든다. K 번째 탐색에서 남은 데이터의 수는 $({1\over 2})^k$ x N이 된다.
• 최악에는 $({1\over 2})^k$ x N = 1이 될 때까지 탐색하게 된다.
• 위 식의 양변에 $2^k$를 곱하면 $2^k$ = N이 되고, 다시 양변에 $\log_{2}$를 취하면 $k = \log_{2}{N}$이 된다.
• K는 탐색 횟수로 N에 따라 시행 횟수가 정해지기 때문에 시간 복잡도는 O($\log_{2}{N}$)이 된다.

---

💾 Space Complexity

• 이진 탐색은 주어진 nums 변수를 계속해서 탐색하기 때문에 공간 복잡도는 nums의 크기인 N만큼 필요하다.
• 따라서 O(N)이다.