binarysearch

Q. 정렬된 배열 num와 찾아야하는 target이 주어집니다. nums 배열에서 target을 찾을 수 있다면 nums의 어디에 있는지 index를 반환해주세요. 이 문제는 O(log n) 시간복잡도를 갖는 알고리즘을 사용하여 풀어야합니다. A. 이 문제는 시간복잡도가 O(log n)을 갖는 알고리즘으로 풀어야합니다. 일반적인 순차탐색은 O(n)이기에 다른 방법을 사용해야합니다. 필요한 알고리즘은 이진탐색입니다. 이진탐색을 정렬된 배열을 반으로 쪼개가며 target을 찾는 방식이여서 시간복잡도가 O(log n)입니다. class Solution: def search(self, nums: List[int], target: int) -> int: def bs(start,end): if start > end..

이진탐색 정렬이 된 배열을 절반씩 줄여가면서 원하는 데이터를 탐색하는 기법 왜 이진탐색을 사용하나요? 이진탐색은 일반적인 탐색(순차적 탐색)보다 정렬된 배열 속에 데이터를 찾아내는 평균적인 시간복잡도가 유리하게 나타납니다. 예를 들면, 1부터 1억까지 정렬된 배열에서 1억을 찾아내라고 해보면, 일반적인 탐색은 1억번의 탐색을 진행해야 1억을 찾아낼 수 있지만, 이진탐색의 경우 절반씩 줄여나가서 탐색하기 때문에 log로 계산해보면 27번 탐색만에 1억을 찾아낼 수 있습니다. 아래 그림을 보며 쉽게 이해해보겠습니다. 위 그림을 보시면 1부터 100까지 정렬되어있는 배열에서 77을 찾아갈 때, 이진탐색으로 찾아가는 과정을 보여주고 있습니다. 100을 반으로 나누고, 찾고있는 77의 숫자를 살펴봅니다. 77은 ..