이분법이란 무엇인가요?

이분법은 [a, b]를 R의 닫힌 구간으로 나누는 방법입니다. 연속 이분법은 다음과 같은 간격 시퀀스 ([an, bn])을 만드는 것입니다. =a, b0=b, 그리고 임의의 자연수 n에 대해 [an+1, bn+1]은 [an, cn]과 같거나 [cn, bn]과 같습니다. 여기서 cn은 [an, bn]을 나타냅니다. 중간점. 확장 정보

일반적인 알고리즘

알고리즘: 이 방법은 데이터 양이 많을 때 적합합니다. 이진 검색을 사용할 때는 데이터를 정렬해야 합니다.

기본 아이디어: 데이터가 오름차순으로 정렬되어 있다고 가정합니다. 주어진 값 키에 대해 시퀀스의 중간 위치 k부터 비교가 시작됩니다.

현재 위치가 arr인 경우. [k] 값이 key 와 같으면 검색이 성공합니다.

key가 현재 위치 값 arr[k]보다 작으면 시퀀스의 전반부인 arr[low, mid- 1];

key가 현재 위치 값 arr[k]보다 큰 경우 시퀀스의 후반부에서 arr[mid+1,high]를 계속 검색합니다.

찾을 때까지 시간 복잡도: O(log(n)) .

참고자료: 이분법(수학 분야의 용어) 바이두백과사전