[LeetCode] 704. Binary Search (Python3)

Description

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.

You must write an algorithm with O(log n) runtime complexity.

풀이

O(log n)에 맞춰 풀어야 하는 문제로, 배열이 정렬됐기 때문에 binary search를 이용하면 쉽게 풀리는 문제이다. 기본적인 binary search 구현을 하면 된다. - left = 0 (최소 index 값), right = list의 길이 - 1(리스트에서 최대 index 값) - left가 right 값 이하일 때 조건에서, - pivot이라는 값을 설정해 (left + right) / 2의 값으로 세팅을 해준 후 - list[pivot]값에 따라 left와 right를 조정해준다. - 이때 left와 right는 pivot ± 1로 설정해주면 된다.

코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot = (left + right) // 2
            if nums[pivot] == target:
                return pivot
            elif nums[pivot] < target:
                left = pivot + 1
            else:
                right = pivot - 1
        return -1