Binary Search
정렬되어 있는 집합에서 원하는 값을 찾는 효율적인 탐색 방법
집합 전체를 확인하는 O(N)복작도가 아닌 O(logN)의 복잡도로 탐색할 수 있다
사용방법
- 원하는 값이 존재살 수 있는 범위를 초기화한다
- 일반적으로 집합의 전체 범위가 첫 조사범위가 된다
- 현재 유효한 범위의 중강값과 찾는 값을 비교하여 조사 범위를 좁힌다
- 중앙값과 같다면 해당 값을 찾았으므로 알고리즘을 종료한다
- 중앙값이 찾는값보다 작다면 조사 범위를 중앙값보다 큰 범위로 좁힌다
- 중앙값이 찾는값보다 크다면 조사 범위를 중앙값보다 작은 범위로 좁힌다
- 유효범위가 남지 않을때까지 찾지 못했다면, 해당 값은 존재하지 않는다
주니어 개발자