이진탐색

• 이진 탐색: 반으로 쪼개면서 탐색하기
  • 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
  • 이미 정렬되어 있다면 매우 빠르게 데이터 찾을 수 있음. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색
  • 변수 3개 사용: 탐색하고자 하는 범위의 시작점, 끝점, 중간점
  • 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교.

시간 복잡도 : O(logN)

반복문으로 구현

def binary_search(array, target, start,end):
  while start<=end: #start>end되면 끝
    mid = (start+end) // 2 #내림
    if arr[mid] == target:
      return mid #찾았으면 중간지점 인덱스 반환
    elif arr[mid] > target: 
      #찾는게 중간지점 값보다 작으면 왼쪽 탐색
      end = mid - 1
    else:
      start = mid +1
  return None


#n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split()))
#전체 원소 입력받기
arr = list(map(int, input().split()))

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

재귀함수로 구현

#재귀함수로 구현한 이진 탐색 
#이진 탐색 소스코드 구현(재귀 함수)
def binary_search(array, target, start, end):
	if start>end:
		return None
	mid = (start+end)//2 #내림
	#찾은 경우 중간점 인덱스 반환
	if array[mid] == target:
		return mid
	#중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
	if array[mid] > target:
		return binary_search(array, target, start, mid - 1 )
	#중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
	else:
		return binary_search(array, target, mid+1, end)

#n(원소의 개수)와 target(찾고자 하는 문자열)을 입력받기
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)