Python 이진 검색은 정렬된 배열에서 항목의 위치를 찾습니다. 목록을 반으로 나눕니다. 지정된 값이 중간 숫자보다 크면 목록의 오른쪽에 초점을 맞춥니다. 그렇지 않으면 검색 시 목록 왼쪽에 있는 번호를 찾습니다.
목록에서 항목의 위치를 어떻게 찾습니까? 이진 검색은 그 중 하나입니다. 이진 검색을 사용하면 정렬된 배열 내에서 요소의 위치를 쉽게 찾을 수 있습니다.
컴퓨터는 특정 항목을 찾기 위해 목록을 검색하는 데 능숙합니다. 컴퓨터가 목록에서 항목을 찾는 데 사용하는 규칙을 검색 알고리즘이라고 합니다. 가장 인기 있는 Python 알고리즘 중 하나는 이진 검색입니다.
이 가이드에서는 바이너리 검색이 무엇이고 어떻게 작동하는지 논의할 것입니다. 프로그램에 이진 검색을 작성하는 방법을 배울 수 있도록 Python에서 이진 검색의 예를 살펴보겠습니다. 시작하겠습니다!
Python 이진 검색이란 무엇입니까?
Python 이진 검색은 정렬된 배열에서 요소의 위치를 찾는 알고리즘입니다. 이진 검색은 목록을 반복적으로 두 부분으로 나눕니다. 그런 다음 검색은 값이 목록의 중간 값보다 높거나 낮은지 비교합니다.
이진 검색을 수행할 수 있는 두 가지 방법이 있습니다. 두 접근 방식 모두 배열의 특정 지점에서 가장 높은 위치와 가장 낮은 위치를 추적하는 데 사용되는 포인터를 설정합니다.
사용할 수 있는 첫 번째 접근 방식은 반복 방법입니다. 이 접근 방식에서는 일련의 명령문이 반복되어 배열에서 요소의 위치를 결정합니다. 파이썬에서는 while을 사용합니다. 이 목적을 위한 루프.
다른 접근 방식은 재귀적 방법입니다. 여기에서 목록의 요소를 찾을 때까지 자신을 계속해서 호출하는 함수를 작성합니다. 재귀적 방법은 앞서 논의한 분할 정복 방식을 사용하고 요소를 찾을 때까지 검색 과정을 반복합니다.
참가자의 81%는 부트캠프에 참석한 후 기술 직업 전망에 대해 더 자신감을 느꼈다고 말했습니다. 지금 부트캠프에 참여하십시오.
부트캠프 졸업생은 부트캠프 시작부터 첫 직장을 찾는 데까지 6개월도 채 걸리지 않았습니다.
이진 검색 트리 Python:단계별
분할, 정복 및 재귀에 대한 모든 이야기로 인해 이진 검색이 어떻게 작동하는지 정확히 추적하지 못할 수 있습니다. 이러한 이유로 이진 검색이 작동하는 방식의 예를 바로 살펴보겠습니다. 다음 목록을 고려하십시오.
| 7 | 9 | 14 | 22 | 34 |
우리는 목록에서 숫자 "22"를 검색할 것입니다.
시작하려면 목록에 두 개의 포인터를 설정합니다. 한 포인터는 목록에서 가장 높은 값을 반영하고 다른 지점은 가장 낮은 값을 반영합니다.
| 낮음 | | | | 높음 |
| 7 | 9 | 14 | 22 | 34 |
다음 단계는 배열에서 중간 요소인 14를 찾는 것입니다. 이 값이 검색하는 값과 같으면 이 값이 반환되어야 합니다.
이 경우 14는 22와 같지 않습니다. 따라서 우리 프로그램은 비교를 수행해야 합니다.
현재 중간 요소의 오른쪽에 있는 요소의 중간 요소와 검색하는 번호를 비교할 것입니다. 검색하는 숫자가 중간 숫자보다 큰 경우에만 이 작업을 수행합니다. 그렇지 않으면 현재 중간 요소의 왼쪽에 있는 중간 요소와 요소를 비교합니다.
숫자 22는 14보다 큽니다. 프로그램은 22를 현재 중간 요소(14)의 오른쪽에 있는 중간 요소와 비교하기 시작합니다. 이 경우 그 숫자는 22입니다. 이것은 우리가 찾고 있는 숫자와 같습니다.
| | | 낮음 | 중간 | 높음 |
| 7 | 9 | 14 | 22 | 34 |
우리는 우리의 중간 가치를 찾았습니다. 이제 프로그램이 해당 숫자의 인덱스 위치를 반환합니다. 이 경우 22의 인덱스 위치는 3입니다(목록은 0에서 시작하여 인덱스됨을 기억하십시오!).
Python에서 이진 검색을 구현하는 방법
파이썬 코드로 손을 더럽히자. 우리는 이전에 논의한 두 가지 접근 방식, 즉 반복 및 재귀 방법을 사용하여 이진 검색의 Python 구현을 탐색할 것입니다.
Python의 반복 이진 검색
반복적인 방법부터 시작하겠습니다. 여기에서 목록의 모든 항목을 반복할 것입니다. 그런 다음 목록에서 중간 값을 찾습니다. 우리가 찾고 있는 가치를 찾을 때까지 계속 그렇게 할 것입니다.
이진 검색 기능
이진 검색을 위한 Python 함수를 정의하는 것으로 시작하겠습니다.
def findValue(numbers, number_to_find): low = 0 high = len(listnumbers - 1 while low <= high: middle = low + (high - low) // 2 if numbers[middle] == number_to_find: return middle elif numbers[middle] < number_to_find: low = middle + 1 else: high = middle - 1 return -1
우리의 함수는 검색할 목록과 목록에서 찾고자 하는 숫자의 두 가지 매개변수를 받습니다.
그런 다음 목록에서 가장 낮은 값과 가장 높은 값에 대한 기본값을 저장하는 두 개의 Python 변수를 선언했습니다. 낮음 목록의 시작 인덱스 값인 0으로 설정됩니다. 높음 목록의 길이에서 1을 뺀 값으로 설정됩니다(목록은 0부터 인덱싱되기 때문에).
다음 단계는 Python while 루프를 선언하는 것이었습니다. 이 루프는 가장 낮은 요소가 가장 높은 숫자보다 작거나 같은 동안 실행됩니다. 이것은 번호가 아직 발견되지 않은 경우에만 루프가 실행됨을 의미합니다.
그런 다음 중간 숫자를 계산합니다. 가장 높은 값에서 가장 낮은 값을 빼서 이 작업을 수행합니다. 그런 다음 2로 나눌 때 해당 숫자의 모듈로(나머지)를 계산합니다. 그런 다음 가장 낮은 숫자의 값에 모듈로를 더합니다.
목록의 중간 숫자가 찾고자 하는 숫자와 같으면 해당 숫자의 위치를 반환합니다.
우리는 새로운 "낮은" 숫자를 중간 위치보다 큰 숫자로 설정했습니다. 이것은 중간 숫자가 우리가 찾고자 하는 숫자보다 작은 경우에 발생합니다. 이렇게 하면 이전의 시각적 예에서와 같이 검색이 목록의 왼쪽 아래로 이동합니다.
그렇지 않으면 "높은" 숫자를 중간 위치보다 1 작은 값으로 설정합니다. 이렇게 하면 검색이 목록의 오른쪽으로 이동합니다.
이것은 low가 high와 같거나 작을 때까지 반복됩니다. 값을 찾지 못하면 -1을 반환합니다. 잠시 후에 그 이유에 대해 이야기하겠습니다.
검색 실행
findValue 외부의 프로그램 맨 아래에 다음 코드를 추가합니다. 기능:
numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find)
if final == -1:
print("This item was not found in the list.")
else:
print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")
검색할 항목 목록을 선언하는 것으로 시작했습니다. 그런 다음 찾고자 하는 숫자인 22를 지정했습니다.
다음으로 findValue()를 호출합니다. 함수를 사용하여 목록을 전달합니다.
여기에서 -1이 이전에 나온 것입니다. 함수에서 반환된 숫자가 -1이면 목록에서 항목을 찾을 수 없음을 의미합니다. 우리의 검색 기능이 음수를 반환할 수 없기 때문에 프로그래머는 종종 이와 같은 상황에서 -1을 사용합니다.
그렇지 않으면 프로그램은 해당 값의 인덱스 위치를 알려주는 메시지를 출력합니다.
코드 반환:
The number 22 was found at index position 3.
이제 숫자 22가 인덱스 위치 3에 나타납니다.
Python의 재귀 이진 검색
재귀를 사용하여 이진 검색을 수행할 수도 있습니다. 여기에서 조건(번호를 찾는 중)이 충족될 때까지 자신을 계속 호출하는 함수를 정의할 것입니다.
재귀 함수 정의
마지막 예에서와 같이 이진 검색을 수행하는 함수를 작성하여 시작하겠습니다.
def findValue(numbers, number_to_find, low, high): if high >= low: middle = low + (high - low) // 2 if numbers[middle] == number_to_find: return middle elif numbers[middle] < number_to_find: return findValue(numbers, number_to_find, middle + 1, high) else: return findValue(numbers, number_to_find, low, middle - 1) else: return -1
코드는 마지막 예제와 다소 유사합니다.
가장 높은 값이 낮은 값보다 크거나 같은지 확인하는 것으로 시작합니다. 그렇다면 우리 프로그램은 -1을 반환합니다. 그렇지 않으면 바이너리 검색을 시작합니다.
마지막 예에서와 동일한 접근 방식을 사용하여 중간 수를 계산합니다. 먼저 가장 높은 값에서 가장 낮은 값을 뺍니다. 그런 다음 해당 값을 2로 나눌 때 모듈로(나머지)를 계산합니다. 마지막으로 가장 낮은 숫자를 추가합니다.
그런 다음 if를 작성했습니다. 바이너리 검색이 어떻게 진행되어야 하는지를 결정하는 문장:
- 가운데 숫자가 찾고 있는 숫자와 같으면 해당 숫자의 위치가 반환됩니다.
- 중간 숫자가 우리가 찾고 있는 것보다 작으면 findValue() 함수가 다시 호출됩니다. 이번에는 낮음 값 중간 값보다 큰 값으로 설정됩니다.
- 중간 숫자가 우리가 찾고 있는 것보다 크면 findValue() 함수가 호출됩니다. "높음" 값은 중간 값보다 1 작은 값과 같습니다.
메인 프로그램 작성
이제 메인 프로그램을 작성하는 일만 남았습니다.
numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find, 0, len(numbers) - 1)
if final == -1:
print("This item was not found in the list.")
else:
print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")
우리의 주요 프로그램은 이전 예제 막대와 동일합니다. findValue()에 두 개의 새 매개변수를 전달합니다. 기능:낮고 높음.
알고리즘이 재귀적이기 때문에 이 작업을 수행해야 하며 함수에서 해당 값을 할당할 수 없습니다. 함수에 값을 할당하면 함수가 실행될 때마다 해당 값이 재설정되어 검색 알고리즘이 중단됩니다.
코드 반환:
The number 22 was found at index position 3.
우리는 이전과 동일한 결과를 받았습니다. 이 예에서는 이진 검색을 수행하기 위해 반복 프로그램 대신 재귀 프로그램을 사용했습니다.
Python 이진 검색을 언제 사용해야 하나요?
이진 검색은 숫자 목록을 검색하는 효율적인 방법입니다. 이 검색은 선형 검색보다 더 효율적입니다. 바이너리 방법은 정렬된 목록의 중간을 찾는 즉시 검색을 절반으로 줄이기 때문입니다.
목록은 이진 검색을 사용하여 검색하기 전에 숫자로 정렬되어야 한다는 점에 유의하는 것이 중요합니다. 이진 검색을 수행하기 전에 숫자가 오름차순으로 정렬되어 있는지 확인하십시오.
Python 복잡성 분석의 이진 검색
이진 검색의 복잡성은 무엇입니까? 좋은 질문입니다.
이진 탐색 알고리즘은 O(1)의 최상의 경우 복잡도를 갖습니다. 이것은 첫 번째 비교가 검색 중인 항목과 같을 때 발생합니다.
이진 검색의 평균 및 최악의 경우 복잡도는 O(log n)입니다. 즉, 목록에서 검색할 항목의 수에 따라 검색을 수행하는 데 걸리는 시간이 대수적으로 늘어납니다.
결론
이진 검색은 목록에서 값의 인덱스 위치를 찾는 효율적인 방법입니다.
이진 검색이 실행될 때마다 검색은 목록을 두 부분으로 나눕니다. 검색은 귀하가 찾고 있는 번호에 가장 가까운 목록 측면에 초점을 맞춥니다.
검색이 실행될 때마다 프로그램이 검색해야 하는 숫자의 양이 절반으로 줄어듭니다.
Python에 대해 자세히 알아보려면 Python 학습 방법 가이드를 읽어보세요.