원하는 탐색 범위를 두 부분으로 분할해서 찾는 방식
L, R 값을 가지며, M(=(L+R)/2)값과 원하는 값을 비교하며 값을 탐색함!
정렬된 배열에서만 적용 가능
[https://wootool.tistory.com/62](https://t1.daumcdn.net/cfile/tistory/221D4A3F5705041A1F)
https://wootool.tistory.com/62
파라메트릭 서치 유형의 문제를 이분 탐색으로 풀 수 있음
각 경우를 만족하는 최대/최소 값을 이분 탐색으로 찾는 것!
구현 ㄱㄱ!
노드의 왼쪽 자식에 붙은 자식들은 모두 해당 노드보다 값이 작고, 노드의 오른쪽 자식에 붙은 자식들은 모두 해당 노드보다 값이 큰,, 그런 트리!
장점
단점
최악의 경우에 편향 트리가 될 수 있고, 이 경우 검색 속도의 이점을 볼 수 없다
10, 20, 30, 40, 50, 60과 같이 정렬된 친구를 삽입하는 경우..
링크드 리스트 한 줄이 생기고, 60을 탐색하기 위해서는 결국 줄줄이 찾아가야 한다.
https://yoongrammer.tistory.com/71
50, 15, 62, 80, 7, 54, 11를 삽입하는 과정
https://yoongrammer.tistory.com/71
60을 탐색하는 과정B-Tree