728x90
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(n)이다.
또한 문제에서 명시적으로 O(log n) 시간 복잡도로 해결하라고 요구하고 있는데,
O(log n) 복잡도를 가지는 대표적인 알고리즘은 이진 탐색이다!
풀이: 이진탐색
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
r = mid - 1
else:
l = mid + 1
return -1
728x90
