이진 탐색-기초 소스코드

순차 탐색 소스코드

def sequential_serch(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_serch(n, target, array))

생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요

(입력) 5 apple

앞서 적은 원소 개수 만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.

(입력) banana orange apple watermelon strawberry

3

---

재귀 함수로 구현한 이진 탐색 소스코드

def binary_serach(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_serch(array, target, start, mid - 1)
    #중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
    	return binary_serch(array, target, mid + 1 end)
        
# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split())
# 전체 원소 입력받기
array = list(map(int, input().split())

# 이진 탐색 수행 결과 출력
result = binary_serch(array, target, 0, n - 1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

10 7

(입력) 5 4 15 2 7 0 85 8 9 11

5

---

반복문으로 구현한 이진 탐색 소스코드

def binary_serch(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(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split())
#전체 원소 입력받기
array = list(map(int, input().split()))

#이진 탐색 수행 결과 출력
result = binary_serch(array, target, 0, n - 1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

10 3

(입력) 5 4 15 2 7 0 85 8 9 11

원소가 존재하지 않습니다.