[항해99] 이진탐색

이진탐색?

"정렬된" 배열에서 어떤 값을 찾는다면 어떤 값을 기준으로 큰 지, 작은 지만 알면 굉장히 빠른 속도로 찾을 수 있다.

log2(N)의 속도로 어떤 값을 찾는 것인데, 1억개도 27번만 연산하면 원하는 원소를 찾을 수 있다는 거!

 

구현

두 개의 점과 그 점의 중간 점이 한 직선에 있다고 생각하자.

 

만약에 중간 점이 우리가 원하는 값보다 크면, 중간점을 왼쪽으로 옮겨줄거고, 작다면 오른쪽으로 옮길 것이다.

중간점을 왼쪽으로 옮기려고 하면 오른쪽 점을 중간 점 위치로 옮기는 것이고,

즁간점을 오른쪽으로 옮기려고 하면 왼쪽 점을 중간 점 바로 다음 위치로 옮기면 된다!

def binary_search(nums, target):
    def bs(start, end):
        if start > end:
            return -1

        mid = (start + end) // 2

        if nums[mid] < target:
            return bs(mid + 1, end)
        elif nums[mid] > target:
            return bs(start, mid - 1)
        else:
            return mid

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

33. Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/

Search in Rotated Sorted Array - LeetCode

 

배열이 주어지는데, 배열이 돌아갔다. 돌아가기 전 배열의 시작점을 찾은 뒤, 현 배열의시작지점~ 이전 배열의 시작부분 바로 앞까지가 이전배열의 끝부분이니 이부분을 현배열의 뒤에 붙여주고 이진 탐색을 진행하면 풀 수 있다.

이진탐색 자체가 어렵다기보단, 이진탐색을 위해 돌아간 배열을 다시 원 배열로 돌리는 과정에서 어려움을 느낄 수 있다.

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def bs(lst, start, end):
            if start > end:
                return -1
            
            mid = (start + end) // 2
            if lst[mid] < target:
                return bs(lst, mid + 1, end)
            elif lst[mid] > target:
                return bs(lst, start, mid - 1)
            else:
                return mid
            

        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        added = nums + nums[:left]

        result = bs(added, left, len(added) -1)
        return result if result == -1 else result % len(nums)

두 배열의 교집합

https://leetcode.com/problems/intersection-of-two-arrays/

Intersection of Two Arrays - LeetCode

파이썬에서는 이진탐색 라이브러리가 이미 있다. bisect라는 모듈인데, 리스트와 target(int)를 넣으면 그 target을 몇 번 인덱스에 넣어야 하는지를 알려준다. 그렇다면 몇 번 인덱스에 넣어야 하는 지랑 지금 들어있는 원소가 같다면 원소를 찾은 게 된다.

import bisect
from typing import List


class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if not nums1 or not nums2:
            return []
        
        result = set()
        nums2.sort()
        for n1 in nums1:
            idx = bisect.bisect_left(nums2, n1)
            if len(nums2) > idx and n1 == nums2[idx]:
                result.add(n1)
        
        return list(result)

두 수의 합 2 

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Two Sum II - Input Array Is Sorted - LeetCode

이진탐색을 활용하는 듯 하지만, 단순 합을 구하는거라, 그냥 투포인터 문제라고 생각해도 상관없다.

양 끝점에서부터 합이 작으면 왼쪽 점을 오른쪽으로 한칸, 합이 크면 오른쪽 점을 왼쪽으로 한 칸 움직이다 보면 정답이 정확히 하나 나온다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i = 0
        j = len(numbers) -1
        
        while i<j:
            s = numbers[i] + numbers[j]
            if s == target:
                return [i + 1 , j + 1]
            
            if s > target:
                j-=1
            else:
               i+=1 
        
        return []