DIL(Daily what I Learn) 1

오늘은 알고리즘 문제를 풀었습니다.

leetcode에서 제공하는 문제입니다.

바이너리 서치 문제

1번 문제는 바이너리 서치를 구현하라는 문제입니다. 문제를 보면 몇 가지 키워드를 뽑아낼 수 있습니다.

정렬된 Integer, O(log N)을 뽑아낼 수 있는데 이 키워드로 추론할 수 있는 정렬 방법은 바이너리 서치 입니다.

우선 바이너리 서치를 쓰기 위해선, item의 크기 비교가 가능해야하고, 정렬된 array여야 합니다.

그 후 아래의 로직을 반복합니다.

# 1. 0 ~ n-1 중에서 중간 값을 찾습니다.
# 2. 중간값과 타겟을 비교합니다.
#	2-1. 중간값과 타겟이 같으면 반환합니다.
#	2-2. 중간값이 타겟보다 클 경우, 0 ~ mid -1 중에 target이 있을 것입니다.
#	2-3. 중간값이 타겟보다 작을 경우, mid +1 ~ 0 중에 target이 있을 것입니다.
# 3. 위 로직을 다 돌았는데 찾지 못할 경우, target은 해당 array에 없습니다.

위 방식을 활용하여 코드를 작성하면 아래와 같습니다.

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

        left_cursor, right_cursor = 0, len(nums)-1

        while left_cursor <= right_cursor:
            mid = (left_cursor + right_cursor) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right_cursor = mid - 1
            else:
                left_cursor = mid + 1
        
        else:
            return -1