정렬되지 않은 배열에서 앞뒤로 검색

정렬되지 않은 배열 - 배열은 동일한 유형의 요소 모음으로 구성된 데이터 구조입니다. 정렬되지 않은 배열은 요소의 순서가 무작위인 구조입니다. 즉, 삽입 시 이전 요소의 순서에 관계없이 요소가 마지막 요소에 추가되고 이러한 배열에서 검색하면 검색 알고리즘의 도움이 발생하지 않습니다. 요소 위치 지정에 대한 패턴이 부족합니다.

Search - 배열에서 검색한다는 것은 배열에서 특정 요소를 찾는 것을 의미하며, 원하는 요소의 위치를 ​​반환하거나 해당 요소가 배열에 있는지 여부를 지정하는 bool 문을 반환할 수 있습니다.

• 앞으로 검색 - 배열에서 앞으로 검색한다는 것은 0번째 인덱스(즉, 첫 번째 요소)부터 시작하여 배열의 선형 검색 순회를 수행한다는 의미입니다.

• 역방향 검색 - 배열을 역방향으로 검색한다는 것은 (n-1)번째 인덱스(즉, 마지막 요소)부터 시작하여 배열의 선형 검색 순회를 수행하는 것을 의미합니다.

문제 설명

검색 요소 x가 주어지면 다음과 같은 경우 x가 존재하는지 확인하세요. -

• 동일한 크기의 요소로 구성된 배열, 정수 배열.

• 다양한 크기의 요소로 구성된 배열, 문자열 배열.

예 1

으아악 으아악

설명 - 주어진 배열에서 두 번째 인덱스에 4가 나타납니다.

예 2

으아악 으아악

설명 - 주어진 배열에 "high"가 존재하지 않습니다.

솔루션

위에서 언급했듯이 정방향 검색은 첫 번째 요소부터 시작되고 역방향 검색은 마지막 요소부터 시작됩니다. 이 두 가지 방법을 결합하면 배열의 전반부와 후반부를 동시에 검사하므로 배열의 요소를 검색하는 시간을 두 배로 줄일 수 있습니다.

요소가 배열에 나타나는지 확인하려면 배열의 첫 번째 요소와 마지막 요소로 first와 last를 정의하세요. 첫 번째 또는 마지막 요소가 필수 요소이면 true를 반환하고, 그렇지 않으면 첫 번째 요소를 1만큼 증가시키고 마지막 요소를 1만큼 감소시키며 요소를 찾을 때까지 계속합니다. 순회가 완료될 때 first와 last가 같으면 요소를 찾을 수 없으면 false가 반환됩니다.

의사코드

으아악

예: C++ 구현

아래 프로그램에서는 정수 배열의 첫 번째 사례를 사용합니다. 필요한 요소를 찾기 위해 첫 번째와 마지막 요소를 확인하면서 첫 번째와 다음 변수를 가져옵니다. 요소가 발견되면 true를 반환하고, 그렇지 않으면 다음 요소로 이동하여 다시 확인합니다.

으아악

출력

으아악

시간 복잡도 - 양쪽에서 검색하면 시간이 절반으로 단축되므로 O(n/2)입니다.

공간 복잡성 - O(1)

예

아래 프로그램에서는 문자열 배열의 두 번째 사례를 사용합니다. 필요한 요소를 찾기 위해 첫 번째와 마지막 요소를 확인하면서 첫 번째와 다음 변수를 가져옵니다. 요소가 발견되면 true를 반환하고, 그렇지 않으면 다음 요소로 이동하여 다시 확인합니다.

으아악

출력

으아악

시간 복잡도 - 양쪽에서 검색하면 시간이 절반으로 단축되므로 O(n/2)입니다.

공간 복잡성 - O(1)

결론

요약하자면, 배열의 정방향 및 역방향 검색은 두 요소를 동시에 검사하므로 시간 소모가 절반으로 줄어든다는 점을 제외하면 일반적인 선형 검색과 유사합니다. 이는 정렬되지 않은 배열에서 검색하는 최악의 경우 시간 복잡도를 O(n)에서 O(n/2)로 변환합니다.

위 내용은 정렬되지 않은 배열에서 앞뒤로 검색의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!