정렬되고 회전된 배열에서 요소를 검색하는 C++ 프로그램

점을 중심으로 회전된 정렬된 배열을 얻습니다. 또한 배열에서 검색할 수 있는 키도 얻습니다. 이 회전된 배열에서 요소를 검색하는 데 사용되는 논리는 -

• 먼저 배열의 중간 요소를 찾습니다. 키가 존재하면 해당 키가 배열에 존재함을 반환합니다.

• 키가 중앙에 없으면 배열의 왼쪽 부분(왼쪽에서 가운데로)이 정렬되어 있는지 확인할 수 있습니다. 정렬되어 있으면 왼쪽에서 키를 찾을 수 있고, 그렇지 않으면 오른쪽(mid+1, 오른쪽)에서 키를 찾을 수 있습니다

• 가운데에 키가 없고 왼쪽 부분이 정렬되지 않은 경우 오른쪽 부분을 정렬한 다음 오른쪽 부분에 키가 있는지 확인하거나 왼쪽 부분을 검색합니다. 오른쪽 부분의 배열

• 그렇지 않으면 찾을 수 없는 상태로 반환됩니다.

아래에서 몇 가지 입력 및 출력 시나리오를 살펴보겠습니다. -

요소들로 구성된 배열이 있다고 상상해 보세요. 예를 들어 2, 5, 7, 9, 11이 회전하면 5, 9, 11, 2, 7이 됩니다. 배열 키가 2라고 가정합니다.

으아아아

키가 지정된 배열에 없는 또 다른 시나리오를 가정해 보겠습니다.

으아아아

알고리즘

다음 단계는 이를 달성하는 방법입니다.

• 배열의 중간 요소를 찾으세요.

• 배열을 두 부분으로 나눕니다. (가운데 = 왼쪽 + 오른쪽) / 2

• key가 중간 요소인지 확인하세요.

• Else if , 배열의 왼쪽에 있는 요소를 확인하고 정렬됩니다

• 그렇지 않은 경우 올바른 요소를 확인하세요(mid+1, 오른쪽)

• 그렇지 않은 경우 왼쪽 부분을 정렬하고 확인하세요

• 그렇지 않으면 찾을 수 없는 요소를 반환합니다.

예

예를 들어 배열 "2,3,4,5,6,7,8"이 있고 회전된 배열이 "5,6,7,8,2,3,4"라고 가정합니다. 이 배열의 키는 2입니다.

이 작업의 C++ 구현은 다음과 같습니다. -

으아아아

출력

으아아아

결론

이 문제를 해결하는 또 다른 방법은 배열 회전의 피벗점이나 인덱스를 찾은 다음 가장자리에서 이진 검색을 수행하는 것입니다. 우리의 방법은 문제를 해결하기 위해 단 한 번의 이진 검색만 필요합니다. 배열 검색 및 정렬을 볼 때마다 검색 방법 중 하나로 이진 검색을 고려해야 합니다.

위 내용은 정렬되고 회전된 배열에서 요소를 검색하는 C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!