35. Search Insertion Position

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums) - 1
        if target > nums[end]:
            return end + 1
        if target < nums[start]:
            return start

        while start<end:
            mid = (start+end)//2

            if target > nums[mid]:
                start = mid + 1
            else:
                end = mid
        
        return start

큰 틀은 이분검색이지만, 리스트 양 끝쪽에 타겟이 들어가는 경우를 알고리즘 안에서 해결하지 못했다.
그래서 그냥 케이스를 나눠서, start보다 target이 작으면 0을 리턴, 반대로 target이 가장크면 끝 인덱스를 리턴하도록 만듬.

다른 풀이가 궁금해서 포스트를 찾아봤는데, 내 풀이가 양 끝은 못 담는 이유를 찾은것 같다.

Come on, forget the binary search pattern/template! Try understand it!

글의 핵심은, 단순히 루프를 만들때나 양 끝단을 잡을때 기계적으로 만들지 말고, edge case를 계속 생각하면서 흐름을 만들라는 얘기다. 앞서 두 이분탐색 문제를 풀때, 대충 만들어도 풀렸지만, 이번 문제는 좀더 딥한 로직을 묻는것 같다.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums)

        while start<end:
            mid = end + (start - end)//2

            if target > nums[mid]:
                start = mid + 1
            else:
                end = mid
        
        return start

조금 더 간단히 짜보고 넘어감