[LeetCode] 704. Binary Search (Python)

• 이진 검색 알고리즘 이용
• target보다 중간 값이 작으면 증가시켜가야 하고
• 크면 감소시켜가야 하고
• 같으면 그 mid 값이 index 값이니 리턴하면 됨

Solution

from typing import List


class Solution:
    # O(log n)으로 풀기
    def search(self, nums: List[int], target: int) -> int:
        lt, rt = 0, len(nums) - 1

        while lt <= rt:
            mid = (lt + rt) // 2

            if nums[mid] == target:
                return mid

            if nums[mid] < target:
                mid += lt
                lt += 1
                continue

            if nums[mid] > target:
                mid -= rt
                rt -= 1

        return -1

Reference

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