이진 탐색

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18] 배열이 주어질 때 4가 어느 위치에 있는지

이진 탐색을 통해 찾아라.

 

arr = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

def binary_search(arr,  target,  start,  end):
  if start > end:
    return None
  mid = (start+end)//2
  
  if arr[mid] == target:
    return mid
  elif arr[mid] > target:
    return binary_search(arr,  target,  start,  mid-1) #arr[mid]=target이 아니니까
  else:
    return binary_search(arr,  target,  mid + 1,  end)
  

target = 4
start = 0
end = len(arr)-1  
result = binary_search(arr,  target,  start,  end)

if result == None:
  print("값이 없음")
else:
  print(result+1,  "번째에 있음")