[코드트리 조별과제] 이진탐색

이진탐색

시간복잡도

O(logN)

• 루프 한 번 돌 때마다 다루는 구간의 길이는 반으로 감소, 구간의 길이가 1이 될 때까지 계속 반복해서 탐색
  • ⇒ 루프 내부의 시간복잡도: O(N)
  • ⇒ 루프는 약 logN번 돌게 됨

이진탐색의 단점

• 반드시 정렬이 되어야 함
• 배열이 정렬된 상태가 아니라면 정렬을 하기 위한 추가적인 연산을 필요로 함

 정리

• 탐색을 여러 번 진행해야 한다면 이진탐색을 사용하는게 좋음
• 가장 큰 값이나 값을 딱 한개만 찾는다면 굳이 이진탐색을 사용할 이유가 없음
• 이진탐색 시 이중연결리스트를 사용하게 되면 mid 위치를 찾는데 O(N)의 시간이 걸리므로 O(logN)보다 시간이 더 걸림

---

Lower Bound

: 원하는 값 target 이상이 처음으로 나오는 위치

• = target 보다 같거나 큰 원소의 위치들 중 가장 작은 값을 출력해야 함
• 작은 값을 구하기 위해 min_idx라는 변수를 활용해 초기값으로 답이 될 수 없는 최댓값인 arr.size를 넣어놓고 문제를 해결

Upper Bound

: 원하는 값 target을 초과하는 값이 최초로 나오는 위치

• UpperBound - LowerBound = 배열 내 수의 갯수
• UpperBound == LowerBound ⇒ 배열 내 값이 없는 것

Custom Bound

: 원하는 값 target 이하의 값이 마지막으로 나오는 위치를 의미

• target 보다 같거니 작은 원소의 위치들 중 가장 큰 값을 출력해야 함
• max_idx = -1