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가 축소 되기 때문에 -를 안해도 지장이 별로 없는 것 같다.


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank Queues: A Tale of Two Stacks  (0) 2017.07.30
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29
Binary Search  (0) 2017.07.28
HackerRank: Basic Problems  (0) 2017.07.25

+ Recent posts