LC 704. Binary Search(이진 탐색)

Binary Search 기본 문제

이진 탐색은 데이터 길이를 반 씩 줄여가며 원하는 값을 찾는 방법이다.
시간 복잡도는 O(logn)으로 선형 탐색 O(n)보다 빠르다.

두 가지 방법으로 구현 가능하다.

1. 재귀를 사용하는 방법

class Solution:
    def search(self, nums: List[int], target: int) -> int:

        # 재귀를 이용한 Binary Search(이진탐색)
        def recursion(start, end):
            # base case: 원하는 값을 찾지 못한 경우
            if start >= end:
                return -1
    
            mid = (start + end) // 2

            if nums[mid] < target:
                return recursion(mid + 1, end)

            elif nums[mid] > target:
                return recursion(start, mid - 1)

            else:
                return mid
                
        return recursion(0, len(nums) - 1)

• 재귀 함수를 만들 때는 base case가 중요하다.

• 배열의 시작(start), 끝(end) 기준으로 start가 end 보다 커지면 재귀함수를 탈출한다.

  • 의미: 반 씩 줄이며 모든 배열을 탐색했는데 원하는 값을 찾지 못했다.

• 중간값(mid)을 구해서 목표값(target)을 비교해 가며 조건문을 나눠준다.

  • nums[mid] < target인 경우 => start를 mid + 1로 바꿔 중간값 이전 데이터 반을 날린다.
  • nums[mid] > target인 경우 => end를 mid - 1로 바꿔 중간값 이후 데이터 반을 날린다.
  • else인 경우는 nums[mid] == target이다.
    원하는 값을 찾았기 때문에 그 인덱스인 mid를 return한다.

• 그림으로 표현한 이진 탐색 재귀
• 초록색 부분이 중간값으로 배열을 나누는 부분.

2. 반복문을 사용하는 방법

    # 반복문을 이용한 Binary Search(이진탐색)
	start, end = 0, len(nums) - 1
    
    # 원하는 값을 찾을 때까지 반복
    while start <= end:
    
        mid = (start + end) // 2
        
        if nums[mid] < target:
            start = mid + 1
            
        elif nums[mid] > target:
            end = mid - 1
            
        else:
            return mid
            
    return - 1

• 좀 더 직관적이다.
• 재귀와 마찬가지로 mid 값을 기준으로 조건에 따라 start, end를 증가 or 감소 시켜주면 된다.