목록2023/10/29 (1)
Rootable의 개발일기
이진 탐색(Binary Search)
데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 시간 복잡도 : O(logN) 구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구하는 영역이다. 📌 탐색 과정 현재 데이터셋의 중앙값을 선택 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택 중앙값 < 타깃 데이터일 때 중앙값 기분으로 오른쪽 데이터셋을 선택 과정 1 ~ 3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료 응용 문제로 특정 범위를 주고 정렬이 가능한 상태에서 O(logN) 내에서 탐색해야 할 때 사용할 수 있다. Reference:
알고리즘
2023. 10. 29. 11:19