이분 탐색 응용 - 중복 타겟 찾기

                                    🗝️ 선형 탐색보다 빠른 탐색을 요구한다. O(log n)

✅ 이미 정렬되어 있다.
✅ 이분탐색을 사용하면 풀릴 것이다.

⚠️ n (0 .. 100000), find fault return [-1, -1], one found = [idx, idx]

                                    class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        result = []

        start = 0
        end = len(nums) - 1

        while start <= end:
            mid = (start + end) / 2
            print("mid: {}".format(mid))

            if nums[mid] > target:
                end = mid - 1
            elif nums[mid] < target:
                start = mid + 1
            else:
                result.append(mid)

        return result if len(result) != 0 else [-1, -1]

                                    [... target ...]
      == target

➡️ case1
[  ...  target target  ... ]
          v == found! -> start = mid + 1

➡️ case2
[  ...  target target  ... ]
                v == found -> end -= 1

➡️ case 3
[  ...  target target  target ... ]
                v == found -> start? end ?

                                    🤔 어차피 묻는 값이 target의 idx의 최대, 최소값이므로,
   이를 기억해두었다가 어디로 이동할지 결정할 수 있을 것 같다.

min = len(nums)
max = 0
➡️ [... target ...]
          mid = i 라고 가정
>>> 발견 위치에 대한 min, max값 업데이트
>>> min = min(min, mid) = i
>>> max = max(max, mid) = i

➡️ [... target ... (checked target) ... target ]
          i - k                          i + j
>>> i - k와 i + j에도 target이 존재한다.

                                    🤔 어차피 mid에서 target이 발견되었으면, mid에서부터 양쪽으로 탐색해도 logn의 시간복잡도를 가진다.

✅ mid를 찾는다 => 이분 탐색 기법

✅ target을 찾았다면 target위치(=mid)부터 양쪽으로 선형 탐색을 시작한다.

✅ target이 아닌 값이 나오는 구간까지 각각 찾아주면된다.
>>> logn + logn으로 logn이된다.

                                    class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        result = []

        start = 0
        end = len(nums) - 1

        while start <= end:
            mid = (start + end) / 2
            print("mid: {}".format(mid))

            if nums[mid] > target:
                end = mid - 1
            elif nums[mid] < target:
                start = mid + 1
            else:
                # add min
                for i in range(start, mid + 1):
                    if nums[i] == target:
                        result.append(i)
                        break

                # add max
                added = False
                for j in range(mid, end + 1):

                    if nums[i] != target:
                        result.append(i - 1)
                        break

                break

        return result if len(result) != 0 else [-1, -1]

                                    🖊️ 로직을 변경하자

✅ 아닌 값이 나오는 것을 확인하지 말고, 맞는 값을 모두 넣고 가장 큰 idx만 빼서 result에 넣자
>>> stack을 사용하면 될 것 같다.

                                    class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        result = []

        start = 0
        end = len(nums) - 1

        while start <= end:
            mid = (start + end) / 2
            print("mid: {}".format(mid))

            if nums[mid] > target:
                end = mid - 1
            elif nums[mid] < target:
                start = mid + 1
            else:
                # add min
                for i in range(start, mid + 1):
                    if nums[i] == target:
                        result.append(i)
                        break

                # add max
                stack = []
                for j in range(mid, end + 1):
                    if nums[j] == target:
                        stack.append(j)
                    else:
                        break
                result.append(stack.pop())
                break

        return result if len(result) != 0 else [-1, -1]