[Python] [Algorithm] 이진탐색

arr에 찾고자 하는 숫자가 있으면 index 리턴.
중간값으로 계속 줄여나가면서 탐색하는 방법.
없으면 -1 리턴

O(log n)

arr = [1,2,3,5,6,7,8,9,10,11]

def binarySearch(arr, targetNum):
  start = 0
  end = len(arr) - 1
  while(start <= end):
    midIndex = (start + end) // 2
    if arr[midIndex] == targetNum:
      return midIndex
    elif arr[midIndex] < targetNum:
      start = midIndex + 1
    elif arr[midIndex] > targetNum:
      end = midIndex -1
    print("start :",start,"end :", end)

  print(midIndex)
  return -1

print(binarySearch(arr, 8))
print(binarySearch(arr, 4))