704. Binary Search

배열에서 target과 같은 숫자에 해당하는 index를 찾아 출력하는 문제이다.

문제에서 O(log n) 알고리즘을 사용하라고 명시되어 있다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if target not in nums:
                return -1
            elif nums[i] == target:
                return i
            

처음에는 O(log n)이 뭔지 몰라서 이렇게 했으나 시간초과..
도저히 안되겠다 싶어 문제를 다시 읽어보고 O(log n)을 검색해봤는데,
중간값을 지정해서 맞으면 그걸 출력하고, 작거나 크면 범위를 좁혀가면서 출력값을 찾는 알고리즘이였다.
근데 어떻게 해야할지 몰라서 솔루션을 여러개 보고 따라해봤는데 사소한거 하나하나에도 런타임이 달라졌다.

가장빠른 코드

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

글자수, 띄어쓰기 등에도 속도가 많이 변했고
가장 크리티컬하게 시간이 단축된 원인은 m에 붙인 int이다.
integer인걸 미리명시해줌으로써 시간을 단축시키는건지.. 신기하다