이진 탐색

** 정의

배열이 정렬되있다고 가정할 때,

 

 

**효율성

import math

math.log2(100000000) # 26.575424759098897

1억번은 연산해야 할 때, 이진 탐색을 사용하면 26번만 탐색하면 된다.

 

**관련 문제

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

Search in Rotated Sorted Array - LeetCode

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

Intersection of Two Arrays - LeetCode

https://leetcode.com/problems/binary-search/

Binary Search - LeetCode

 

 

** 풀이 (위 순서대로)

<Search in Rotated Sorted Array>

def bs_rotated(nums, target):
    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

    if not nums:
        return -1

    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)

 

 

 

<Intersection of Two Arrays>

def intersec_arrays(nums1, nums2):
    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)

 

 

<Binary Seach>

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)

assert binary_search(nums=[-1, 0, 3, 5, 9, 12], target=9) == 4
assert binary_search(nums=[-1, 0, 3, 5, 9, 12], target=2) == -1