이진 검색 알고리즘을 사용하여 숫자의 세제곱근을 찾는 Java 프로그램

큐브 루트는 이 값을 연속으로 세 번 곱하면 원래 값이 되는 정수 값입니다. 이 기사에서는 이진 검색을 사용하여 숫자의 세제곱근을 찾는 Java 프로그램을 작성합니다. 숫자의 세제곱근을 찾는 것은 이진 검색 알고리즘을 적용한 것입니다. 이 기사에서는 이진 검색을 사용하여 세제곱근을 계산하는 방법을 자세히 설명합니다.

입출력 예시

으아아아

예를 들어 64의 세제곱근은 4이고 출력은 4입니다.

으아아아

예를 들어 216의 세제곱근은 6이고 출력값은 6입니다.

이진 검색

이진 검색은 요소(예: 정렬된 배열의 키)를 찾는 데 사용되는 알고리즘입니다. 바이너리 알고리즘은 다음과 같이 작동합니다

• 배열이 "arr"이라고 가정합니다. 배열을 오름차순 또는 내림차순으로 정렬합니다.

• 낮음 = 0, 높음 = n-1(n = 요소 수)을 초기화하고 mid를 중간 = 낮음 + (높음-낮음)/2로 계산합니다. arr[middle] == key이면 배열의 중간 인덱스인 middle을 반환합니다.

• 키 값이 arr[middle] 요소보다 작으면 높은 인덱스를 중간 인덱스 -1로 설정하고, 키 값이 중간 요소보다 크면 낮은 인덱스를 중간 인덱스 +1로 설정합니다.

찾고 싶은 요소를 찾을 때까지 이진 검색을 계속하세요.
낮음이 높음보다 큰 경우 'arr' 배열에 키 값이 없기 때문에 false를 직접 반환합니다.
이진 검색을 사용하여 키를 찾는 예

질문

정렬된 정수 배열 arr = [1, 3, 5, 7, 9, 11]이 있는 경우 이진 검색을 사용하여 요소의 인덱스(예: 키 = 7)를 찾습니다.

솔루션

low = 0 및 high = 5(배열의 마지막 인덱스)를 초기화합니다.
while 루프의 첫 번째 반복은 중간 인덱스 mid = low+(high-low)/2

• 를 제공합니다.

중앙값 = 0+(5-0)/2 = 2.
arr[mid] 값은 5로 키 값 7보다 작습니다. 따라서 low= mid+1 = 3으로 업데이트합니다.
while 루프의 두 번째 반복에서는 low+(high-low)/2를 사용하여 중간 인덱스 mid = 4를 제공합니다.
arr[mid] 값은 9로, 키 값 7보다 큽니다. 따라서 high = 3(mid - 1)을 업데이트합니다.
while 루프의 세 번째 반복은 중간 인덱스 mid = 3을 제공합니다.
arr[mid]는 7이며 키 값과 같습니다. 따라서 중간 인덱스인 3을 반환합니다.
그래서 주어진 배열에서 키의 인덱스는 7이고 이진 검색 알고리즘을 사용하여 인덱스 3을 찾았습니다.
이진 검색을 사용하여 입방체 근을 찾는 알고리즘

1단계

- 숫자 'n'을 고려하고 low=0 및 right=n(주어진 숫자)을 초기화합니다.

2단계

- mid = low + (high-low)/2를 사용하여 낮은 값과 높은 값의 중앙값을 구합니다.

3단계

− mid * mid * mid 값을 구하고, mid * mid * mid == n인 경우 mid 값을 반환합니다.

4단계

- 중간 값이 n보다 작으면 낮음=중간+1, 그렇지 않으면 높음=중간-1

5단계

- 값을 찾을 때까지 2~4단계를 반복합니다. Example

의 중국어 번역은

Example

입니다.

이 예에서는 이진 검색 알고리즘을 사용하여 값의 세제곱근을 찾습니다. 우리는 사용자 정의 클래스 'BinarySearchCbrt'를 생성하고 'cuberoot' 함수에서 숫자의 세제곱근을 찾기 위한 이진 검색 코드를 구현했습니다. 이제 사용자 정의 클래스 객체를 생성하고 'number'라는 정수 변수를 초기화한 후, 클래스 객체를 사용하여 'cuberoot' 함수를 호출하면 원하는 출력이 표시됩니다.

으아아아

출력

으아아아

시간 복잡도: O(NlogN) 보조 공간: O(1)

그래서 이 글에서는 Java에서 이진 검색 알고리즘을 사용하여 숫자의 세제곱근을 찾는 방법에 대해 논의했습니다.

위 내용은 이진 검색 알고리즘을 사용하여 숫자의 세제곱근을 찾는 Java 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!