99클럽 코테 스터디 13일차 TIL + 이진 탐색

 

오늘의 공부 키워드

• 이진 탐색
• 35.Search Insert Position

 

이진 탐색의 개념

이진 탐색은 다음과 같은 단계를 거칩니다:

1. 초기 설정: 배열의 처음과 끝을 가리키는 두 개의 포인터(left와 right)를 설정합니다.
2. 중간 요소 찾기: left와 right의 중간 지점을 계산하여 mid로 설정합니다.
3. 비교:
   • nums[mid]가 타겟 값과 같으면, mid를 반환합니다.
   • nums[mid]가 타겟 값보다 작으면, 타겟 값은 mid의 오른쪽에 있으므로 left를 mid + 1로 이동시킵니다.
   • nums[mid]가 타겟 값보다 크면, 타겟 값은 mid의 왼쪽에 있으므로 right를 mid - 1로 이동시킵니다.
4. 반복: left가 right보다 작거나 같을 때까지 2-3 단계를 반복합니다.
5. 결과: 탐색 범위가 없으면 타겟 값이 배열에 없음을 의미하며, 이때 삽입 위치를 반환할 수 있습니다.

예시

정렬된 배열 nums = [1, 3, 5, 7, 9]와 타겟 값 target = 7을 찾는 예시를 통해 설명하겠습니다:

1. 초기 설정: left = 0, right = 4 (배열의 인덱스 범위)
2. 중간 요소 찾기: mid = (0 + 4) // 2 = 2
   • nums[2] = 5
3. 비교: 5 (nums[mid]) < 7 (target)
   • left = mid + 1 = 3
4. 반복:
   • 새로운 중간 요소 찾기: mid = (3 + 4) // 2 = 3
   • nums[3] = 7
5. 비교: 7 (nums[mid]) == 7 (target)
   • 타겟 값을 찾았으므로 mid = 3 반환

이 과정에서 타겟 값을 효율적으로 찾을 수 있습니다.

 

35. Search Insert Position

이 문제는 주어진 정렬된 배열에서 특정 값을 찾는 문제입니다. 만약 해당 값을 찾으면 그 인덱스를 반환하고, 찾지 못하면 그 값을 정렬된 순서에 맞게 삽입할 때의 인덱스를 반환하는 문제입니다. 이 문제는 이진 탐색 알고리즘을 사용하면 O(log n)의 시간 복잡도로 해결할 수 있습니다.

이진 탐색은 배열의 중간 요소와 타겟 값을 비교하고, 비교 결과에 따라 탐색 범위를 절반으로 줄여가는 방식으로 동작합니다. 정렬된 배열에서 빠르게 값을 찾거나 삽입할 위치를 찾기에 적합합니다.

 

예시

예를 들어보겠습니다:

1. 입력: nums = [1, 3, 5, 6], target = 5 출력: 2 (타겟 값 5는 배열의 2번 인덱스에 존재합니다.)
2. 입력: nums = [1, 3, 5, 6], target = 2 출력: 1 (타겟 값 2는 배열에 없으며, 2가 들어가면 [1, 2, 3, 5, 6]가 되므로 인덱스 1에 삽입됩니다.)
3. 입력: nums = [1, 3, 5, 6], target = 7 출력: 4 (타겟 값 7은 배열에 없으며, 7이 들어가면 [1, 3, 5, 6, 7]가 되므로 인덱스 4에 삽입됩니다.)

코드

def searchInsert(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return left

 

이 코드를 한 단계씩 설명하면 다음과 같습니다:

1. left와 right 포인터를 배열의 시작과 끝으로 설정합니다.
2. 배열이 유효한 범위 (left가 right보다 작거나 같을 때)에서 반복합니다.
3. 중간 인덱스 mid를 계산합니다.
4. 중간 값 nums[mid]가 타겟 값과 같으면 mid를 반환합니다.
5. nums[mid]가 타겟 값보다 작으면 타겟은 오른쪽에 있으므로 left를 mid + 1로 이동합니다.
6. nums[mid]가 타겟 값보다 크면 타겟은 왼쪽에 있으므로 right를 mid - 1로 이동합니다.
7. 반복이 끝난 후에도 값을 찾지 못하면, 타겟 값을 삽입해야 하는 위치는 left가 됩니다.

이진 탐색을 사용하여 이 문제를 해결하면 O(log n)의 시간 복잡도로 효율적으로 해결할 수 있습니다.

 

오늘의 회고

 

• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자
• 새로운 개념을 배울수 있어서 좋았다.