이진 탐색(Binary Search) ?
순차 탐색 (Sequential Search) ?
def sequential_search(n, target, array):
for i in range(n):
if array[i] == target:
return i+1
print("생설할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0])
target = input_data[1]
print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()
print(sequential_search(n, target, array))
- 정렬되어 있어야만 사용 가능.
- 범위를 반 씩 좁혀가며 빠르게 탐색하는 알고리즘.
- Target값과 중간점(Minddle) 위치 값을 반복적으로 비교
- 스무 고개 처럼 👍
이진 탐색 소스코드 구현(재귀 함수)
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
else:
return binary_search(array, target, mid + 1, end)
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = binary_search(array, target, 0, n-1)
if result == None:
print("원소가 존재하지 않습니다.")
else:
print(result + 1)
이진 탐색 소스코드 구현(반복문)
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
return None
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = binary_search(array, target, 0, n - 1)
if result == None:
print("원소가 존재하지 않습니다.")
else:
print(result + 1)
- '생각하는 프로그래밍' 저자 존 벤틀리의 말에 따르면
binary search를 제대로 작성한 프로그래머는 10%내외라 할정도로 실제 구현은 까다롭다.
- 코테에 자주 나오니 가급적 외우길 권장
- 처리해야 할 데이터의 개수가 1,000만 이상이면 이진 탐색과 같이 O(logN)의 속도를 내야하는 경우가 많다.