PYTHON의 이진 검색

이 튜토리얼에서는 Python을 사용하여 이진 검색 알고리즘을 적용하여 주어진 목록에서 요소의 인덱스 위치를 찾는 방법을 배웁니다.

소개

이진 검색은 목록에서 특정 요소를 찾는 알고리즘입니다. 수천 개의 요소 목록이 있고 특정 요소의 인덱스 위치를 가져와야 한다고 가정합니다. 이진 검색 알고리즘을 사용하면 요소의 인덱스 위치를 매우 빠르게 찾을 수 있습니다.

검색 알고리즘에는 여러 가지가 있지만 그 중 이진 검색이 가장 많이 사용됩니다.

이진 검색 알고리즘을 적용하려면 목록의 요소를 정렬해야 합니다. 요소가 정렬되지 않은 경우 먼저 정렬하세요.

이진 검색의 개념을 이해해 봅시다.

이진 검색의 개념

이진 검색 알고리즘에서는 다음 방법을 사용하여 요소 위치를 찾을 수 있습니다.

재귀적 방법
반복 방법

분할 정복 접근법 기술 다음에는 재귀적 방법이 따릅니다. 이 방법에서는 목록에서 요소를 찾을 때까지 함수가 계속해서 호출됩니다.

반복 방법에서 요소의 인덱스 위치를 찾기 위해 일련의 명령문이 여러 번 반복됩니다. 그만큼 ~하는 동안 루프는 이 작업을 수행하는 데 사용됩니다.

이진 검색은 각 목록 인덱스를 검색할 필요가 없기 때문에 선형 검색보다 더 효과적입니다. 이진 검색 알고리즘을 구현하려면 목록을 정렬해야 합니다.

이진 검색을 단계별로 구현해 보겠습니다.

정렬된 요소 목록이 있고 인덱스 위치 45를 찾고 있습니다.

[12, 24, 32, 39, 45, 50, 54]

그래서 우리는 목록에 두 개의 포인터를 설정하고 있습니다. 하나의 포인터는 다음과 같은 더 작은 값을 나타내는 데 사용됩니다. 낮은 두 번째 포인터는 호출된 가장 높은 값을 나타내는 데 사용됩니다. 높은 .

다음으로, 우리는 가운데 배열의 요소입니다.

 mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer)

이제 검색된 요소와 중간 인덱스 값을 비교해 보겠습니다. 이 경우, 32 같지 않다 넷 다섯. 따라서 요소를 찾으려면 추가 비교를 수행해야 합니다.

우리가 검색하는 숫자가 mid와 같으면. 그런 다음 돌아오세요 중반 그렇지 않으면 추가 비교로 이동합니다.

검색할 숫자가 해당 숫자보다 큽니다. 가운데 숫자를 비교해보자 N 오른쪽에 있는 요소 중 중간 요소를 사용하여 중반 그리고 낮게 설정 낮음 = 중간 + 1.

그렇지 않으면 비교하십시오. N 와 더불어 중간 요소 왼쪽에 있는 요소 중 중반 그리고 설정 높은 에게 높음 = 중간 - 1.

찾고 있는 번호를 찾을 때까지 반복합니다.

Python에서 이진 검색 구현

먼저, 반복 방법으로 이진 검색을 구현합니다. 일련의 명령문을 반복하고 목록의 모든 항목을 반복합니다. 검색이 완료될 때까지 중간값을 찾아보겠습니다.

반복 방법의 다음 프로그램을 이해해 봅시다.

파이썬 구현

 # Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low <= 1 2 high: # for get integer result mid="(high" + low) check if n is present at list1[mid] n: high="mid" - smaller, compared to the left of else: return element was not in list, -1 initial list1 24, 32, 39, 45, 50, 54] function call n) !="-1:" print('element index', str(result)) list1') < pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 4 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above program -</p> <ul> <li>We have created a function called <strong>binary_search()</strong> function which takes two arguments - a list to sorted and a number to be searched.</li> <li>We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, <strong>high</strong> to <strong>len(list1)</strong> - 1 and mid as 0.</li> <li>Next, we have declared the <strong>while</strong> loop with the condition that the <strong>lowest</strong> is equal and smaller than the <strong>highest</strong> The while loop will iterate if the number has not been found yet.</li> <li>In the while loop, we find the mid value and compare the index value to the number we are searching for.</li> <li>If the value of the mid-index is smaller than <strong>n</strong> , we increase the mid value by 1 and assign it to The search moves to the left side.</li> <li>Otherwise, decrease the mid value and assign it to the <strong>high</strong> . The search moves to the right side.</li> <li>If the n is equal to the mid value then return <strong>mid</strong> .</li> <li>This will happen until the <strong>low</strong> is equal and smaller than the <strong>high</strong> .</li> <li>If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.</li> </ul> <p>Let&apos;s understand the recursive method of binary search.</p> <h2>Recursive Binary Search</h2> <p>The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.</p> <p>Let&apos;s understand the above program using the recursive function.</p> <h3>Python Program</h3> <pre> # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;) </pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 2 </pre> <p> <strong>Explanation</strong> </p> <p>The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.</p> <ul> <li>We calculate the middle number as in the last program.</li> <li>We have used the <strong>if</strong> statement to proceed with the binary search.</li> <li>If the middle value equal to the number that we are looking for, the middle value is returned.</li> <li>If the middle value is less than the value, we are looking then our recursive function <strong>binary_search()</strong> again and increase the mid value by one and assign to low.</li> <li>If the middle value is greater than the value we are looking then our recursive function <strong>binary_search()</strong> again and decrease the mid value by one and assign it to low.</li> </ul> <p>In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the <strong>binary_search()</strong> function.</p> <p>This is because we can&apos;t assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.</p> <h2>Complexity</h2> <p>The complexity of the binary search algorithm is <strong>O(1)</strong> for the best case. This happen if the element that element we are looking find in the first comparison. The <strong>O(logn)</strong> is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.</p> <h2>Conclusion</h2> <p>A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.</p> <p>We have discussed both methods to find the index position of the given number.</p> <hr></=>

설명:

위 프로그램에서 -

우리는 다음과 같은 함수를 만들었습니다. 바이너리 검색() 두 개의 인수, 즉 정렬할 목록과 검색할 숫자를 취하는 함수입니다.
목록에 가장 낮은 값과 가장 높은 값을 저장하기 위해 두 개의 변수를 선언했습니다. 낮은 값에는 초기 값이 0으로 할당됩니다. 높은 에게 렌(목록1) - 1과 중간은 0입니다.
다음으로 우리는 다음을 선언했습니다. ~하는 동안 다음과 같은 조건으로 루프를 반복합니다. 가장 낮은 는 와 동일하고 더 작습니다. 제일 높은 숫자를 아직 찾지 못한 경우 while 루프가 반복됩니다.
while 루프에서 중간 값을 찾고 인덱스 값을 검색 중인 숫자와 비교합니다.
중간지수의 값이 작은 경우 N , mid 값을 1 증가시켜 에 할당합니다. 검색이 왼쪽으로 이동합니다.
그렇지 않으면 중간 값을 줄이고 이를 높은 . 검색이 오른쪽으로 이동합니다.
n이 중간 값과 같으면 다음을 반환합니다. 중반 .
이는 다음 날짜까지 발생합니다. 낮은 는 와 동일하고 더 작습니다. 높은 .
함수의 끝에 도달하면 해당 요소는 목록에 존재하지 않습니다. 호출 함수에 -1을 반환합니다.

이진 검색의 재귀적 방법을 이해해 봅시다.

Java에서 arraylist를 정렬하는 방법

재귀 이진 검색

재귀 방법은 이진 검색에 사용될 수 있습니다. 여기서는 조건을 충족할 때까지 자신을 계속 호출하는 재귀 함수를 정의하겠습니다.

재귀함수를 이용하여 위의 프로그램을 이해해보자.

파이썬 프로그램

 # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;)

산출:

 Element is present at index 2

설명

위 프로그램은 이전 프로그램과 유사합니다. 재귀 함수와 기본 조건을 선언했습니다. 조건은 가장 낮은 값이 가장 높은 값보다 작거나 같다는 것입니다.

마지막 프로그램에서와 같이 중간 숫자를 계산합니다.
우리는 만약에 이진 검색을 진행하기 위한 명령문입니다.
중간 값이 찾고 있는 숫자와 같으면 중간 값이 반환됩니다.
중간 값이 값보다 작으면 재귀 함수를 살펴봅니다. 바이너리 검색() 다시 mid 값을 1 증가시키고 low에 할당합니다.
중간 값이 우리가 찾고 있는 값보다 크면 재귀 함수 바이너리 검색() 다시 한 번 mid 값을 1만큼 줄이고 low에 할당합니다.

마지막 부분에서 우리는 메인 프로그램을 작성했습니다. 이전 프로그램과 동일하지만 유일한 차이점은 두 개의 매개변수를 전달했다는 것입니다. 바이너리 검색() 기능.

이는 재귀함수에서 low, high, mid에 초기값을 할당할 수 없기 때문입니다. 재귀 함수가 호출될 때마다 해당 변수에 대한 값이 재설정됩니다. 그러면 잘못된 결과가 나옵니다.

복잡성

이진 검색 알고리즘의 복잡성은 다음과 같습니다. 오(1) 최선의 경우를 위해. 우리가 찾고 있는 요소가 첫 번째 비교에서 발견되면 이런 일이 발생합니다. 그만큼 오(로그인) 이진 검색의 최악이자 평균 사례 복잡성입니다. 이는 우리가 찾고 있는 요소를 찾기 위해 수행되는 검색 횟수에 따라 달라집니다.

결론

이진 검색 알고리즘은 목록의 요소를 검색하는 가장 효율적이고 빠른 방법입니다. 불필요한 비교는 생략합니다. 이름에서 알 수 있듯이 검색은 두 부분으로 나누어집니다. 우리가 찾고 있는 숫자에 가까운 목록의 측면에 초점을 맞춥니다.

우리는 주어진 숫자의 인덱스 위치를 찾는 두 가지 방법을 모두 논의했습니다.

TechCodeview

소개