[TIL] 이분 탐색 Binary Search

1920 수 찾기 문제를 풀다가 이분 탐색이 분류에 있길래 정리해본다 

이분 탐색 Binary Search 

정렬되어 있는 리스트 또는 배열에서 탐색 범위를 절반씩 좁혀가며
원하는 값 Target 의 존재 위치/ 존재 여부를 찾는 알고리즘

 

 

이분 탐색 특징 

단계마다 탐색 범위를 반으로 나누기 때문에 시간 복잡도는 O(logN) 이다 

단, 배열이 정렬되어 있어야만 사용 가능하다는 단점이 있다 

 

Quick Sort 와 유사한 접근 방법을 사용해서, Pivot 대신 mid 값을 계산하여

left 로 탐색 범위의 왼쪽 경계, right 로 탐색 범위의 오른쪽 경계를 설정하고

찾는 대상과 mid 값을 비교하여 left, right, mid 값을 변경하며 범위를 줄인다 

* Quick Sort 공부 자료

 

이분 탐색 코드

백준 1920 수 찾기 문제 참고