[Leetcode] Binary Search

문제 출처

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

Binary Search - LeetCode

 

문제 해설

• 정수로 구성된 리스트(nums)에 정수(target)가 포함되어 있는지 확인하는 문제
  • nums는 오름차순으로 정렬된 상태
  • target이 포함되어 있으면 nums에서 target이 위치한 인덱스를 포함되어 있지 않으면 -1을 반환
• 탐색하는 데 걸리는 시간 복잡도는 O(logN)가 되어야 한다.

 

문제 풀이

# source: https://leetcode.com/problems/binary-search/?envType=study-plan&id=binary-search-i


class Solution:
    def search(self, nums: list[int], target: int) -> int:
        start = 0
        end = len(nums)

        if target > nums[-1] or target < nums[0]:
            return -1

        while start <= end:
            mid = (end + start) // 2

            if nums[mid] == target:
                return mid

            if nums[mid] > target:
                end = mid - 1
            elif nums[mid] < target:
                start = mid + 1

        return -1

• 리스트가 정렬되어 있고, 시간 복잡도가 O(logN)이 되어야 하므로 이진 탐색을 이용

 

Github

• https://github.com/limseunghyun95/Algorithm_study/blob/150439300f6dcde3c72eddaf191de14ca1303b3f/leetcode/binary_search.py