검색 구현은 항상 어렵지만 불가능하지는 않습니다.
실생활에서는 패턴 없이 검색합니다. 우리는 그것이 놓일 수 있다고 생각하는 곳으로 이동합니다. 대부분의 경우 어떤 패턴도 따르지 않습니다.
프로그래밍 세계에서도 같은 일이 가능합니까?
아니! 프로그램에서 물건을 검색하려면 어떤 패턴이 있어야 합니다. 우리는 이 글에서 다양한 검색 패턴을 따르는 몇 가지 알고리즘을 보게 될 것입니다.
프로그래밍 세계에서 찾을 수 있는 여러 알고리즘이 있습니다. 이 기사에서 가장 중요하고 가장 많이 사용되는 알고리즘에 대해 논의할 것입니다. 나머지 알고리즘은 쉽게 배울 수 있습니다.
검색이란 이 문서에서 배열의 요소를 검색하는 것을 말합니다.
하나씩 살펴보겠습니다.
목차
선형 검색
이름은 선형 검색 알고리즘이 선형 패턴을 따라 배열의 요소를 검색한다는 것을 암시합니다. 알고리즘은 배열의 처음부터 요소 검색을 시작하고 요소를 찾을 때까지 끝까지 이동합니다. 필요한 요소를 찾으면 프로그램 실행을 중지합니다.
알고리즘을 더 잘 이해할 수 있도록 몇 가지 멋진 그림으로 선형 검색 알고리즘을 설명하겠습니다.
검색 패턴을 주의 깊게 관찰하면 프로그램 실행에 걸리는 시간이 최악의 경우 O(n)이 걸린다는 것을 알 수 있습니다. 분석할 알고리즘의 최악의 경우 시간 복잡도를 고려해야 합니다. 따라서 알고리즘의 시간 복잡도는 O(n)입니다.
선형 검색 알고리즘의 구현을 살펴보겠습니다.
선형 검색 구현
이제 선형 검색 알고리즘을 잘 이해했습니다. 코드로 손을 더럽힐 때입니다. 먼저 선형 검색을 구현하는 단계를 살펴보겠습니다. 그런 다음 코딩을 시도합니다. 할 수 없더라도 걱정하지 마십시오. 나중에 코드를 알려드리겠습니다.
선형 검색 알고리즘을 구현하는 단계를 살펴보겠습니다.
- 요소 배열(행운의 숫자)을 초기화합니다.
- 세 개의 인수, 배열, 배열의 길이, 검색할 요소를 받아들이는 search_element라는 함수를 작성하세요.
- search_element(arr, n, 요소):
- 주어진 배열을 반복합니다.
- 현재 요소가 필수 요소와 같은지 확인하십시오.
- 그렇다면 True를 반환합니다.
- 루프를 완료한 후 실행이 아직 함수에 있으면 해당 요소가 배열에 없는 것입니다. 따라서 False를 반환합니다.
- 주어진 배열을 반복합니다.
- search_element 함수의 반환 값을 기반으로 메시지를 인쇄합니다.
마지막으로 위의 단계를 통해 선형 검색 알고리즘을 구현하는 코드를 작성합니다.
선형 검색 알고리즘의 구현을 완료했습니까? 나는 희망한다. 완료했으면 다음 코드로 교차 확인합니다.
완료하지 못했다면 걱정하지 마세요. 아래 코드를 보고 어떻게 구현했는지 알아보세요. 많은 노력없이 얻을 수 있습니다.
## searching function def search_element(arr, n, element): ## iterating through the array for i in range(n): ## checking the current element with required element if arr[i] == element: ## returning True on match return True ## element is not found hence the execution comes here return False if __name__ == '__main__': ## initializing the array, length, and element to be searched arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] n = 10 element_to_be_searched = 6 # element_to_be_searched = 11 if search_element(arr, n, element_to_be_searched): print(element_to_be_searched, "is found") else: print(element_to_be_searched, "is not found")
먼저 배열에 있는 요소로 프로그램을 실행합니다. 그런 다음 배열에 없는 요소로 실행합니다.
선형 탐색 알고리즘의 시간 복잡도는 O(n)입니다.
다른 패턴으로 좀 더 줄일 수 있을까요?
네, 할 수 있습니다. 한번 볼까.
이진 검색
이진 검색 알고리즘은 항상 배열의 중간 요소를 확인합니다. 이 알고리즘은 정렬된 배열에서 요소를 검색합니다.
이진 검색 알고리즘은 배열을 반복하고 중간 요소를 확인한 다음 발견되면 프로그램을 중지합니다. 그렇지 않으면 가운데 요소가 필요한 요소보다 작으면 가운데 요소에서 배열의 왼쪽 부분을 검색에서 생략합니다. 그렇지 않으면 중간 요소가 필요한 요소보다 크면 검색에서 중간 요소의 배열 오른쪽 부분을 생략합니다.
각 반복에서 이진 검색 알고리즘은 요소를 검색할 영역을 줄입니다. 따라서 검사 횟수는 선형 검색 알고리즘에서 수행된 검사 횟수보다 적습니다.
그림은 이진 검색 알고리즘을 더 잘 이해하는 데 도움이 됩니다. 확인해 봅시다.
이진 검색 알고리즘의 시간 복잡도는 O(log n)입니다. 반복할 때마다 검색 영역의 길이가 절반으로 줄어듭니다. 기하급수적으로 줄어들고 있습니다.
이진 검색 구현
먼저 이진 검색 알고리즘을 구현한 다음 코드를 구현하는 단계를 볼 것입니다. 이진 검색 알고리즘 구현을 완료하는 단계를 살펴보겠습니다.
- 요소(행운의 숫자)로 배열을 초기화합니다.
- 세 개의 인수, 정렬된 배열, 배열의 길이, 검색할 요소를 받아들이는 search_element라는 함수를 작성하세요.
- search_element(정렬된_arr, n, 요소):
- 배열 반복을 위해 인덱스 변수 i를 초기화합니다.
- 다음으로 배열의 검색 영역을 유지하기 위해 두 개의 변수를 초기화합니다. 여기서는 인덱스를 나타내므로 시작 및 종료를 as라고 합니다.
- i가 배열의 길이보다 작아질 때까지 반복합니다.
- 시작 값과 끝 값을 사용하여 검색 영역의 중간 인덱스를 계산합니다. 그것은 (시작 + 끝) // 2가 될 것입니다.
- 검색 영역의 중간 색인 요소가 필수 요소와 같은지 확인하십시오.
- 그렇다면 True를 반환합니다.
- 그렇지 않으면 중간 색인 요소가 필수 요소보다 작으면 검색 영역의 시작 색인을 중간 + 1로 이동합니다.
- 그렇지 않으면 가운데 색인 요소가 필수 요소보다 크면 검색 영역의 끝 색인을 중간 – 1로 이동합니다.
- 배열 i의 인덱스를 증가시킵니다.
- 루프를 완료한 후 실행이 아직 함수에 있으면 해당 요소가 배열에 없는 것입니다. 따라서 False를 반환합니다.
- search_element 함수의 반환 값을 기반으로 메시지를 인쇄합니다.
선형 검색 알고리즘 구현과 유사한 코드를 작성해 보십시오.
…
코드를 받으셨나요?
예, 아래 코드와 비교하십시오. 아니요, 걱정하지 마세요. 아래 코드로 구현을 이해하십시오.
## searching function def search_element(sorted_arr, n, element): ## array index for iteration i = 0 ## variables to track the search area ## initializing them with start and end indexes start = 0 end = n - 1 ## iterating over the array while i < n: ## getting the index of the middle element middle = (start + end) // 2 ## checking the middle element with required element if sorted_arr[middle] == element: ## returning True since the element is in the array return True elif sorted_arr[middle] < element: ## moving the start index of the search area to right start = middle + 1 else: ## moving the end index of the search area to left end = middle - 1 i += 1 return False if __name__ == '__main__': ## initializing the array, length, and element to be searched arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] n = 10 element_to_be_searched = 9 # element_to_be_searched = 11 if search_element(arr, n, element_to_be_searched): print(element_to_be_searched, "is found") else: print(element_to_be_searched, "is not found")
요소가 존재하고 어떤 경우에는 존재하지 않는 다양한 경우로 코드를 테스트하십시오.
결론
이진 검색 알고리즘은 선형 검색 알고리즘보다 훨씬 효율적입니다. 이진 검색 알고리즘을 위해 배열을 정렬해야 하지만 선형 검색 알고리즘에서는 그렇지 않습니다. 정렬에는 시간이 걸립니다. 그러나 효율적인 정렬 알고리즘을 사용하면 이진 검색 알고리즘과 좋은 조합을 형성할 수 있습니다.
이제 Python에서 가장 널리 사용되는 알고리즘에 대해 잘 알고 있습니다.
다음으로 인기 있는 자체 호스팅 검색 소프트웨어를 찾으십시오.
행복한 코딩 🙂 🧑💻