이분 탐색

언제 사용할까?

: 완탐으로 풀려고 했는데, 시간복잡도가 어마어마 할때

이분탐색은 시간복잡도가 n / 2 아니고 왜 logN일까?

• 참고 사이트
  https://neos518.tistory.com/145

• 8개의 오름차순된 데이터가 있음. 84를 찾는 다고 하면?
  1 , 3, 4, 17 , 84 , 90 , 92 , 110

• 1) s : 0 , end : 7 / mid : 3
  v[3] vs 84 : 84가 크므로 -> s에 mid + 1
• 2) s : 4 , end : 7 / mid : 5
  v[5] : 90 vs 84 // 84가 작으므로 -> e에 mid -1
• 3) s : 4 , end : 4 / mid : 4
  84 vs 84 : 3번만에 찾음
• 결론 : 8개의 데이터를 log8, 3의 비용으로 찾음.