PHP의 이진 검색

이진 검색이란 무엇인가요?

이진 검색은 정렬된 배열(또는 목록)에서 대상 값의 위치를 ​​효율적으로 찾기 위해 사용되는 검색 알고리즘입니다. 검색 범위를 반복적으로 절반으로 나누고 중간 요소를 대상 값과 비교하는 방식으로 작동합니다.

이진 검색 알고리즘은 다음 단계를 따릅니다.

• 전체 정렬된 배열로 시작하세요.

• 왼쪽 포인터를 배열의 첫 번째 요소로 설정하고 오른쪽 포인터를 마지막 요소로 설정합니다.

• 왼쪽 및 오른쪽 포인터의 평균(정수 나누기)으로 중간 지수를 계산합니다.

• 중간 지수의 값과 목표값을 비교해보세요.

• 중간 값이 목표 값과 같으면 검색이 성공하고 알고리즘이 인덱스를 반환합니다.

• 목표 값이 중간 값보다 큰 경우 왼쪽 포인터를 mid + 1로 업데이트하여 검색 범위의 왼쪽 절반을 제거합니다.

• 대상 값이 중간 값보다 작은 경우 오른쪽 포인터를 중간 - 1로 업데이트하여 검색 범위의 오른쪽 절반을 제거합니다.

• 목표 값을 찾거나 검색 범위가 비어 있을 때까지(왼쪽 포인터가 오른쪽 포인터보다 큼) 3~7단계를 반복합니다.

• 검색 범위가 비어 있고 목표 값을 찾을 수 없으면 알고리즘은 목표 값이 배열에 존재하지 않는다고 결론을 내리고 -1 또는 적절한 표시를 반환합니다.

이진 검색은 O(log n)의 시간 복잡도를 갖는 매우 효율적인 알고리즘입니다. 여기서 n은 배열의 요소 수입니다. 각 단계에서 검색 범위를 절반으로 나누어 검색 범위를 빠르게 좁혀 요소 수가 많아도 빠른 검색이 가능하므로 대규모로 정렬된 배열에 특히 효과적입니다.

이진 검색 PHP 프로그램

방법 1 - 반복 사용

예

으아아아

출력

으아아아

방법 2 - 재귀 사용

예

으아아아

출력

으아아아

결론

요약하자면 이진 검색은 정렬된 배열에서 목표 값을 효율적으로 찾을 수 있는 강력한 알고리즘입니다. 반복 및 재귀라는 두 가지 일반적인 구현을 제공합니다. 반복 방법은 while 루프를 사용하여 대상 값을 찾거나 범위가 비어 있을 때까지 검색 범위를 반복적으로 절반으로 분할합니다. 구현이 간단하며 대부분의 시나리오에 적합합니다. 반면에 재귀적 방법은 재귀 함수를 사용하여 이진 검색을 수행합니다. 반복 방법과 동일한 논리를 따르지만 루프 대신 함수 호출을 사용합니다. 재귀 이진 검색은 더 깔끔한 구현을 제공하지만 함수 호출 스택 조작으로 인해 오버헤드가 약간 더 높을 수 있습니다. 전반적으로 두 방법 모두 이진 검색 작업을 수행하는 효율적이고 안정적인 방법을 제공합니다.

위 내용은 PHP의 이진 검색의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!