C++를 사용하여 검색이 성공할 때마다 요소를 두 배로 늘려 요소를 반복적으로 검색합니다.

이 기사에서는 정수 배열과 키워드가 제공됩니다. 우리는 배열에서 키를 반복적으로 찾아야 하며, 조회할 때마다 키를 두 배로 늘려야 합니다. 이 작업을 수행할 때 배열에 없는 값을 반환해야 합니다.

몇 가지 입력 시나리오를 보고 다양한 상황에서 메서드가 어떻게 작동하는지 확인하세요

키가 1인 배열 [1,2,6,3,7,4,9]를 살펴보겠습니다.

으아아아

1을 찾으면 2로 두 배로 늘립니다.

2개를 찾으면 4개로 두 배로 늘립니다.

4개를 찾으면 8개로 두 배로 늘립니다.

배열에 요소 8이 없기 때문에 8을 반환합니다

또 다른 경우에는 키가 1인 배열 {2, 3, 7, 8, 5, 9}를 고려합니다.

으아아아

입력 배열에 요소 1이 없기 때문에 1을 그대로 반환합니다.

알고리즘

• 작은 배열의 경우 이진 검색 수행의 복잡성이 낮기 때문에 배열 요소를 정렬합니다.

• 배열의 요소가 키 값과 일치할 때마다 키 값을 두 배로 늘리고 배열을 다시 검색하여 새 키와 일치하는 요소를 찾습니다.

• 배열에 이중 키 값과 일치하는 요소가 없을 때까지 이 단계를 반복하세요.

• 최종 키 값은 얻은 출력입니다.

예(벡터 ADT 사용)

배열을 정렬하여 이 방법을 구현하기 시작합니다. 그 후에는 질문에 나온 대로 정확하게 검색하고 두 번 수행합니다. 바이너리 검색을 통해 최적화된 검색을 수행합니다. 동일한 논리를 적용하여 C++ 프로그램을 살펴보겠습니다. -

으아아아

출력

으아아아

예(벡터 ADT 없음)

C++ 프로그램도 동일한 논리를 따르지만 벡터 추상 데이터 유형을 사용하지 않습니다.

배열을 정렬하여 이 접근 방식을 구현하기 시작합니다. 그런 다음 질문에서 요구하는 작업을 수행하고 검색을 수행합니다. 우리는 바이너리 검색을 통해 최적화합니다.

으아아아

출력

으아아아

결론

STL 이진 검색 방법을 사용하여 요소 발견 여부에 따라 true 또는 false를 반환합니다. 사용자 정의 이진 검색 구현을 사용할 수도 있습니다. STL은 뛰어난 정렬 및 검색 방법을 제공하므로 구현에 대해 지나치게 생각하지 않고도 문제를 작성할 수 있습니다.

위 내용은 C++를 사용하여 검색이 성공할 때마다 요소를 두 배로 늘려 요소를 반복적으로 검색합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!