704 Binary Search

• 704 Binary Search
  • 문제
  • 조건
  • 예제
  • 해결
    • 1st
      • 1 생각
      • 1 코드
      • 1 결과: 성공
    • 2nd 책 풀이
      • 2 코드

704 Binary Search

문제

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

조건

• $1 \le nums.length \le 10^{4}$
• $-9999 \le nums[i], target \le 9999$
• All the integers in nums are unique.
• nums is sorted in an ascending order

예제

Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

해결

1st

1 생각

• 이진 탐색은 정렬된 배열을 절반으로 쪼개면서 탐색해 나간다
• nums 자체는 유지하면서 찾으려는 값의 인덱스를 찾아간다
• dfs처럼 재귀적으로 범위를 좁혀 나가면 될 것 같다

1 코드

def search(self, nums: List[int], target: int) -> int:
    ans = -1
    
    def recursion(nums, start, end):
        if end < start: 
            return -1

        if start == end:
            if nums[start] == target:
                return start
            else:
                return -1
        
        mid = start + ((end - start) // 2)

        if nums[mid] == target:
            return mid

        if nums[mid] < target:
            return recursion(nums, mid + 1, end)
        else:
            return recursion(nums, start, mid - 1)
    
    ans = recursion(nums, 0, len(nums) - 1)

    return ans

• 문제를 풀면서 조건을 추가해 나가서 가독성이 좋지 않다
• 아래 책풀이의 search_recursion가 위의 코드를 보다 깔끔하게 정리한 것 같다. 위의 코드를 반면교사로… 삼자…
• 말로 설명하면서, 그 설명에 따라 문제를 푸는데, 그러다 보니 나중에 조건이 추가되는 경우가 많다
• 정의하려는 함수의 내용, 파라미터, 결과 값 등으로 미리 조건들을 정리할 줄 알아야 할 것 같다

1 결과: 성공

Runtime: 236 ms
Memory Usage: 15.7 MB

2nd 책 풀이

2 코드

def search_recursion(self, nums: List[int], target: int) -> int:
    def binary_search(left, right):
        if left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                return binary_search(mid + 1, right)
            elif nums[mid] > target: 
                return binary_search(left, mid - 1)
            else:
                return mid
        else:
            return -1

    return binary_search(0, len(nums) - 1)

def search_loop(self, nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2

        if nums[mid] < target: # 우측에 있으므로, 좌를 우측으로 좁힌다
            left = mid + 1
        elif nums[mid] > target: # 좌측에 있으므로, 우를 좌측으로 좁힌다
            right = mid - 1
        else:
            return mid

    return -1

def search_module(self, nums: List[int], target: int) -> int:
    import bisect
    # target을 삽입할 인덱스를 반환
    # target이 이미 존재하면, 이미 존재하는 가장 좌측의 target 앞에 삽입
    idx = bisect.bisect_left(nums, target)
    if idx < len(nums) and nums[idx] == target:
        return idx
    return -1

def search_by_index(self, nums: List[int], target: int) -> int:
    try:
        return nums.index(target)
    except ValueError:
        return -1