Binary Search

Binary Search

---

input = [1,2,3,4,5,6,7,8,9,10]

target = 1
index = 0

min = 0
max = len(input) -1
mid = int(len(input)/2)

step = 1
while (target != input[mid]):
    if input[mid] < target:
        min = mid +1
    else:
        max = mid -1

    mid = int((max+min)/2)
    step +=1

print("target index: %d, steps: %d"%(mid, step))

Points

• length -1
• min은 +1
• max는 -1
  +를 안할 경우 mid값이 변동이 없어서 마지막 위치에 있는 target 값을 못찾는다.
  -를 안할 경우 왼쪽에 있는 값을 step 3번에 찾을 수 있는 것을 4번에 찾는다. int() 때문에 버림이 적용되우 int가 축소 되기 때문에 -를 안해도 지장이 별로 없는 것 같다.