개인적으로 공부하면서 블로그를 작성하고 있으므로 내용이 정확하지 않을 수 있습니다.
잘못된 부분은 지적해주시면 개발자로서 성장하는데 많은 도움이 될 것 같습니다. 😀
이진 탐색이란?
- 오름차순으로 정렬된 리스트에서 특정 값을 찾는 알고리즘이다.
- 오름차순으로 정렬된 리스트를 절반으로 줄여가면서 탐색하는 방법이다.
- BigO : O(log N)
장점
- 검색이 반복될 때 검색 범위가 절반으로 줄어들어 속도가 빠르다.
단점
- 오름차순으로 정렬된 리스트에서만 사용이 가능하다.
동작 방식
List : [ 1, 5, 7, 8, 11, 15, 18 ]
Target : 5첫 번째 탐색
- 리스트에서 가운데 위치한 임의의 값 8을 선택한다.
- 임의의 값 8과 검색 값 5를 비교한다. ( 5 < 8 )
- 검색 값이 임의의 값 좌측에 존재한다는 것을 알 수 있다.
두 번째 탐색
- 8을 기준으로 좌측의 값으로 다시 탐색을 진행한다.
- [ 1, 5, 7 ] 에서 가운데 위치한 임의의 값 5를 선택한다.
- 검색 값과 임의의 값이 같으므로 원하는 값을 찾게된다.
탐색 종료 조건
- 검색 값을 찾았을 때
- 검색 값이 리스트에 존재하지 않을 때
- 위 예시에서는 리스트의 좌측을 탐색해서 검색 값을 찾는데 더 이상 남은 리스트가 존재하지 않게되면 리스트에 검색 값이 존재하지 않는다는것을 알 수 있다.
잘 하고 싶다.