이진 검색은 배열의 요소를 찾는 것뿐만 아니라 방정식의 근과 단조(증가 또는 감소) 함수의 값을 찾는 데에도 사용할 수 있습니다.
단조 함수 f와 이 함수의 일부 값 C가 주어집니다. \(f(x)=C\)와 같은 이 함수의 x 인수 값을 찾습니다.
증가하는 단조 함수의 예:
함수의 값이 주어진 값보다 정확히 크고 정확히 작은 경계를 선택합니다. 이 세그먼트의 중간에 있는 값을 선택하겠습니다. 주어진 것보다 작으면 왼쪽 테두리를 세그먼트 중앙으로 이동합니다. 그렇지 않으면 오른쪽 경계를 이동합니다. 다음으로 경계를 좁히는 과정을 반복합니다. 그러나 문제는 언제 검색을 중지해야 하는가입니다. 자세히 알아보기 여기.
예를 들어, 숫자 x의 제곱근을 찾는 문제를 생각해 보십시오. x(\(\sqrt x\)로 표시됨)의 제곱근은 다음과 같은 숫자 y입니다. < span class="math-tex">\(y^2 = x\).
다음과 같이 문제를 공식화해 봅시다. 주어진 실수 x( \(x >= 1\))에 대해 점 뒤 5자 이상의 정확도를 가진 제곱근.
검색할 세그먼트의 테두리 선택
숫자의 전체 무한대를 확인할 수 없기 때문에 루트 검색의 경계를 정의해야 합니다. 먼저 왼쪽 테두리를 찾아 임의의 음수 점(예: -1)을 선택합니다. 그 값이 주어진 값보다 클 때까지 두 배로 늘릴 것입니다. 올바른 경계를 찾기 위해 임의의 양수 지점(예: 1)을 선택합니다. 이 시점에서 함수의 값이 지정된 값보다 작을 때까지 두 배로 합니다.
또는 검색의 경계를 정확히 알고 있는 경우 왼쪽 경계로 1을 사용하고 숫자 자체를 x로 사용할 수 있습니다. 그 후 현재 세그먼트를 반으로 나누고 가운데를 제곱하고 x보다 크면 윗면을 교체하고 그렇지 않으면 바닥.
최종 구현:
여기서
eps - 솔루션을 찾아야 하는 정확도
x - 우리가 찾고 있는 제곱근의 주어진 숫자,
m - 알고리즘이 실행된 후 결과가 저장될 숫자입니다.
|