[ 알고리즘 ] LeetCode 704. Binary Search

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 1523. Count Odd Numbers in an Interval Range를 풀고 작성한 글입니다.

문제

요구사항

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.

제약사항

• 1 <= nums.length <= 104
• 104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

풀이

접근법

전형적인 이진 탐색(Binary Search)으로 문제를 해결하면 된다.

나의 풀이

접근법을 토대로 문제를 해결하면 아래와 같다.

def solution(nums: list[int], target: int) -> int:
	start, end = 0, len(nums)-1
    while start <= end:
    	middle = (start+end) // 2
        if nums[middle] == target:
        	return middle
        elif nums[middle] > target:
        	end = middle - 1
        else:
       		start = middle + 1
	return -1

다른 풀이

파이썬의 내장 모듈 bisect 내의 메서드들 중 bisect_left 및 bisect_right 메서드를 사용하여 만약 두 값이 동일할 경우 존재하지 않는 숫자이기 때문에 -1 을 반환하고 두 값이 동일하지 않을 경우 bisect_right 메서드 반환값에 1 을 빼거나 bisect_left 반환값에 1 을 더해서 최종 결괏값으로 반환하면 된다.

def another_solution(nums: list[int], target: int) -> int:
	from bisect import bisect_left, bisect_right
    return (bisect_right(nums,target)-1) if bisect_rigt(nums,target) != bisect_left(nums,target) else -1
	

시간 복잡도

이와 같이 문제를 풀 경우 시간 복잡도는 문제에서 요구한 바와 같이 O(logN)이다.