개념
전제조건
정렬된 데이터 집합이여야 함
변수
start = 집합의 시작 원소 위치
end = 집합의 마지막 원소 위치
mid = 집합의 중간 원소 위치
알고리즘
-
데이터 개수가 n인 정렬집합 arr에서 target을 찾는것!
-
strart ≤ end 일 동안 아래 3. ~ 5. 을 반복
-
if arr[mid] == target :
mid 반환 + 종료 // 중간 위치의 왼쪽 확인
-
if arr[mid] > target:
end = mid - 1 // 중간 위치의 왼쪽 확인
-
if arr[mid] < target:
start = mid + 1 // 중간 위치의 오른쪽 확인
필기
- 나는 왜 start, end를 1씩 줄이는게 아니라 절반을 나눈뒤 1씩 증감을 하는지가 의문이였는데, 사실상 그 의문점이 이분(이진)탐색의 전부였다. 아래는 설명전문이다.
-
이진 검색에서 검색 대상이 정렬된 리스트일 때, 리스트에서 찾고자 하는 값을 찾을 때까지 검색 범위를 계속해서 반으로 줄여나갑니다. 따라서, 검색 범위를 좁히는 간격이 늦추는 요소가 될 수 있기 때문에, 가능한 한 빠르게 검색 범위를 좁히기 위해, 중간 위치를 기준으로 좌우의 검색 범위를 균등하게 나누는 것이 좋습니다.
따라서,end = mid - 1을 사용하는 것은, 중간 위치를 기준으로 검색 범위를 왼쪽으로 좁히는 것이므로, 왼쪽과 오른쪽 검색 범위가 균등하게 나누어지는 것입니다. 만약end = end - 1과 같이, 간격을 한 칸씩 줄여나가는 것보다, 중간 위치를 기준으로 좌우 검색 범위를 균등하게 나누는 것이 검색 속도를 높일 수 있습니다.
결론적으로, 검색 범위를 줄이는 속도는 중간 위치를 기준으로 좌우 검색 범위를 균등하게 나누는 것이 빠르기 때문에, 이진 검색에서는end = mid - 1과 같이 중간 위치를 기준으로 좌우 검색 범위를 나누는 것이 일반적입니다.100개라 가정했을때, 타겟이 45정도에 있다면, 이 코드는 다음에 0부터 50 + 1 사이에서 찾겠다고 말하는 것이다. 절반으로 줄여가며 빠르게 찾기! 인것이다.
-
- 순차 탐색 O(n)과 이분 탐색 O(log n), 두 가지를 쓸 수 있는 경우 항상 이분 탐색을 쓰는게 더 좋을까?
-
순차탐색 O(n) vs. 최초 정렬 O(n log n) + 이분 탐색 O(log n)
위를 참고하면 쉽게 이해 가능하다. 이분탐색을 적용하기 위한 최초 정렬과정이 필요하기때문에 (파이썬은 quick sort) 수가 적을경우, 그리고 최악의 상황이 아닌 경우에는 순차탐색이 좋을수 있다. 수를 찾는 횟수가 많아질수록 이분탐색이 유리해진다.
-
코드
절차지향 / 반복문
#이분탐색 / 절차지향 / 반복문 구현
#target = 찾고자 하는 값을 입력받기위함
n , target = list(map(int, input().split()))
n_list = list(map(int, input().split()))
#이분탐색은 항상 정렬된 배열에서만 적용 가능하다
n_list.sort()
start = 0
end = n - 1
ans = 0
while start <= end:
mid = (start + end) // 2
if n_list[mid] == target:
ans = mid
break
elif n_list[mid] > target:
end = mid - 1
elif n_list[mid] < target:
start = mid + 1
print(ans)함수형 / 반복문
#이분탐색 / 함수형 / 반복문 구현
#arr = 리스트
#key = 탐색하고싶은 값
#start, end
def binary(arr, key, start, end):
while start <= end:
mid = (start + end) // 2
if arr[mid] == key:
return mid
elif arr[mid] > key:
end = mid - 1
elif arr[mid] < key:
start = mid + 1
return None
#target = 찾고자 하는 값을 입력받기위함
n , target = list(map(int, input().split()))
n_list = list(map(int, input().split()))
#이분탐색은 항상 정렬된 배열에서만 적용 가능하다
n_list.sort()
result = binary(n_list, target, 0, n-1)
print(result)함수형 / 재귀함수
#이분탐색 / 함수형 / 재귀함수 구현
#arr = 리스트
#key = 탐색하고싶은 값
#start, end
def binary(arr, key, start, end):
mid = (start + end) // 2
if start > end:
return None
if arr[mid] == key:
return mid
elif arr[mid] > key:
return binary(arr, key, start, mid - 1)
elif arr[mid] < key:
return binary(arr, key, mid + 1, end)
#target = 찾고자 하는 값을 입력받기위함
n , target = list(map(int, input().split()))
n_list = list(map(int, input().split()))
#이분탐색은 항상 정렬된 배열에서만 적용 가능하다
n_list.sort()
result = binary(n_list, target, 0, n-1)
print(result)