S.E.B 0.0.8

이진검색 Binary Search

이진검색이란 정렬된 배열에서 타겟을 찾는 검색 알고리즘이다.

대표적인 로그 시간 알고리즘

• 이진 검색은 값을 찾아내는 시간 복잡도가 $O(logn)$

이진탐색트리 ↔ 이진검색

• 이진탐색트리 BST ⇒ 정렬된 구조를 저장하고 탐색하는 자료구조
• 이진검색 ⇒정렬된 배열에서 값을 찾아내는 알고리즘 자체

import math
math.log2(100000000) # 1억 개의 아이템을 27번이면 모두 찾을 수 있다.
>>> 26.57

1부터 100까지 범주에서 상대방이 마음속으로 정한 숫자를 맞추는 마술예시

• 77을 정했다고 가정했을때
• 7번의 비교로 답을 찾을 수 있다

1. 50 보다 큰가 ? (1-100의 중앙값) Yes→ 왼쪽 포인터를 오른쪽으로 이동
2. 75보다 큰가 ? (50-100의 중앙값) Yes
3. 87보다 큰가? (75-100의 중앙값) No→ 오른쪽 포인터를 왼쪽으로 이동
4. 81보다 큰가? (75-87의 중앙값) No
5. 78보다 큰가? (75-81의 중앙값) No
6. 76보다 큰가? (75-78의 중앙값) No
7. 정답은 77인가 ?(76-78) Yes

math.log2(100)
>>> 6.6 #7번

• 처음 중간의 값을 임의의 값으로 선택
• 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식
• 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.
• 단점 : 검색 원리상 정렬된 리스트에만 사용할 수 있다
• 장점 : 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다

데이터가 정렬되어 있고, 어떤 방식으로 들어가 있는지도 알고 있다면 해시탐색 O(1)이 더 빠르다 → 리스트의 길이에 영향을 받지 않고 항상 일정한(상수) 시간안에 결과값을 리턴

def binarySearch(array, value, low, high):
	if low > high:
		return False
	mid = (low+high) / 2
	if array[mid] > value:
		return binarySearch(array, value, low, mid-1)
	elif array[mid] < value:
		return binarySearch(array, value, mid+1, high)
	else:
		return mid