이중 분할
정의
이진 탐색 방법은 순서가 있는 요소의 목록을 입력으로 사용하는 알고리즘입니다.
검색 중인 요소가 목록에 포함되어 있으면 이진 검색은 해당 요소의 위치를 반환합니다. 그렇지 않으면 null을 반환합니다.
기본 아이디어
- 이 방법은 데이터 양이 많을 때 적합합니다.
- 이진 탐색을 사용할 때 데이터를 정렬해야 합니다.
- 데이터가 오름차순으로 정렬되어 있다고 가정하고, 주어진 값 키에 대해 시퀀스의 중간 위치인 mid에서 비교를 시작합니다.
- 현재 위치의 arr[mid] 값이 key와 같으면 검색이 성공합니다.
- 키가 현재 위치 값 arr[mid]보다 작으면 시퀀스의 전반부에서 arr[low,mid-1]을 검색합니다.
- 키가 현재 위치 값인 arr[mid]보다 큰 경우 시퀀스의 후반부에서 arr[mid+1,high]를 찾을 때까지 계속 검색합니다.
시간 복잡도:
