4 분 소요

Binary Search

문제

문제 링크

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5 Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2 Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7 Output: 4

스스로 고민

접근법

  • 정렬된 배열이 제공되고 거기서 타겟 넘버의 인덱스 값을 찾는다.

의사코드

  • 타겟 넘버의 인덱스를 찾는다.
  • 타겟 넘버가 인덱스 0번의 값 보다 작을 경우 리턴 0
  • 타겟 넘버가 마지막 인덱스 값 보다 클 경우 리턴 len(nums)
  • 그 이외의 경우 이진 탐색시작
  • 타겟 값이 중간 값보다 클 경우
    • 가장 왼쪽 값을 중간 값으로 업데이트
    • 중간 값은 현재 중간 값의 절반을 더함 (나머지가 나올 수 있으므로 반올림)
    • 타겟 값이 중간 값보다 작아질 경우
      • 현재 가장 왼쪽 값이 0이 아니고 중간 값도 초기 값이 아니라면
      • 가장 왼쪽 값에서 + 1을 리턴
  • 타겟 값이 중간 값보다 작을 경우
    • 가장 오른 쪽값을 중간 값으로 업데이트
    • 중간 값은 중간 값의 절반을 마이너스 해줌 (나머지가 나올 수 있으므로 반올림)
    • while 문이 false가 될 경우 임계치를 넘었으므로 mid 값 +1 리턴

구현 코드

import math

class Solution:

    def searchInsert(self, nums: List[int], target: int) -> int:

        length = len(nums)

  

        if target in nums:

            x = nums.index(target)

            return x

        elif target < nums[0]:

            return 0

        elif target > nums[length-1]:

            return length

        else:

            mid = int(len(nums)/2)

            left = 0

            right = len(nums)-1

  

            while nums[mid] < target:

                left = mid

                mid += math.ceil(mid/2)

                mid = min(mid, length-1)

            if left != 0 and mid != int(len(nums)/2):

                return left + 1

  

            while nums[mid] > target:

                right = mid

                mid -= math.ceil(mid/2)

            return mid + 1

시간 복잡도와 공간 복잡도

시간 복잡도:

  1. target in nums: 이 부분은 최악의 경우 O(n) 시간이 소요된다. 여기서 n은 nums의 길이
  2. target < nums[0]와 target > nums[length-1]: 이 두 조건은 O(1) 시간이 소요 된다.
  3. 이 외의 경우:
    • mid = int(len(nums)/2): 이 부분은 O(1) 시간이 소요된다.
    • while nums[mid] < target 루프: 이 루프는 최악의 경우 O(log n) 번 반복될 수 있다. 왜냐하면 각 단계마다 탐색 범위가 반씩 줄어들기 때문이다.
    • while nums[mid] > target 루프: 마찬가지로 최악의 경우 O(log n) 번 반복될 수 있다.
    • 최종적으로 각 루프에서 수행되는 작업들은 상수 시간이 소요되므로, 이 부분의 시간 복잡도는 O(log n)다.

따라서 전체 코드의 최악의 경우 시간 복잡도는 O(n) + O(log n)이 됩니다. 대부분의 경우에는 더 작은 O(log n) 시간이 소요될 수 있다.

공간 복잡도:

  • 변수 length, x, mid, left, right는 모두 상수 공간을 사용하므로 O(1) 다.

총 정리하면, 이 코드의 시간 복잡도는 O(n) + O(log n)이며, 공간 복잡도는 O(1)다.

회고 과정

지금 코드에서 뭘 개선할 수 있지?

  • 너무 복잡하다, 가독성도 떨어지고 쉬운 문제라고 생각했는데 내가 헷갈려서 더 오래걸렸던 것 같다.
  • 연산을 좀 더 깔끔하고 한 번에 하면 좋을 것 같아서 최적화를 한 번 해봤다.
class Solution:

    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left
  • 중복되는 연산을 하나로 합치고 최소 조건으로 맞추려고 노력했다.
  • 이제 다른 사람들은 어떻게 했는지 보고 배우는 게 좋을거 같다.

    다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) 
        while (low < high):
            middle = (low + high) //2
            if nums[middle] == target:
                return middle
            elif nums[middle] > target:
                high = middle 
            else:
                low = middle + 1
        return low
  • middle = (low + high) //2 로도 생각을 하지 못 했는데 다음에는 시간을 갖고 더 생각해봐야 겠다.

댓글남기기

참고