이진 검색을 위한 PYTHON 프로그램(재귀 및 반복)

간단히 말해서, 이 검색 알고리즘은 단 한 번의 비교 후에 요소의 절반을 무시하여 이미 정렬된 요소 모음을 활용합니다.

x를 중간 요소와 비교합니다.
x가 중간 요소와 일치하면 중간 인덱스를 반환합니다.
그렇지 않고 x가 중간 요소보다 큰 경우 x는 중간 요소 뒤의 오른쪽(더 큰) 하위 배열에만 놓일 수 있습니다. 그런 다음 오른쪽 절반에 알고리즘을 다시 적용합니다.
그렇지 않고 x가 더 작으면 대상 x는 왼쪽(하단) 절반에 있어야 합니다. 그래서 우리는 왼쪽 절반에 알고리즘을 적용합니다.

재귀를 사용한 이진 검색을 위한 Python 프로그램

파이썬3

# Python 3 program for recursive binary search.> # Modifications needed for the older Python 2 are found in comments.> # Returns index of x in arr if present, else -1> def> binary_search(arr, low, high, x):> > # Check base case> > if> high>> => low:> > mid> => (high> +> low)> /> /> 2> > # If element is present at the middle itself> > if> arr[mid]> => => x:> > return> mid> > # If element is smaller than mid, then it can only> > # be present in left subarray> > elif> arr[mid]>x:> > return> binary_search(arr, low, mid> -> 1> , x)> > # Else the element can only be present in right subarray> > else> :> > return> binary_search(arr, mid> +> 1> , high, x)> > else> :> > # Element is not present in the array> > return> -> 1> # Test array> arr> => [> 2> ,> 3> ,> 4> ,> 10> ,> 40> ]> x> => 10> # Function call> result> => binary_search(arr,> 0> ,> len> (arr)> -> 1> , x)> if> result !> => -> 1> :> > print> (> 'Element is present at index'> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )>

산출

Element is present at index 3

시간 복잡도 : O(로그 n)

보조 공간 : O(logn) [참고: 재귀는 호출 스택을 생성합니다]

반복을 사용한 이진 검색을 위한 Python 프로그램

파이썬3

# Iterative Binary Search Function> # It returns index of x in given array arr if present,> # else returns -1> def> binary_search(arr, x):> > low> => 0> > high> => len> (arr)> -> 1> > mid> => 0> > while> low <> => high:> > mid> => (high> +> low)> /> /> 2> > # If x is greater, ignore left half> > if>

arr[mid]   low = mid + 1  # If x is smaller, ignore right half  elif arr[mid]>x: high = mid - 1 # x가 mid에 존재한다는 의미 else: return mid # 여기에 도달하면 요소가 존재하지 않는 것입니다. return -1 # 배열 테스트 arr = [ 2, 3, 4, 10, 40 ] x = 10 # 함수 호출 결과 = binary_search(arr, x) if result != -1: print('요소가 인덱스에 존재합니다', str(result)) else: print('요소가 배열에 존재하지 않습니다 ')>

산출

Element is present at index 3

시간 복잡도 : O(로그 n)

보조 공간 : ㅇ(1)

내장된 bisect 모듈을 사용하는 이진 검색을 위한 Python 프로그램

단계별 접근 방식:

이 코드는 이진 검색을 지원하는 bisect 모듈을 가져옵니다.
arr 배열과 x를 검색할 요소를 입력으로 사용하는 Binary_search_bisect() 함수가 정의됩니다.
이 함수는 정렬 순서를 유지하기 위해 x가 삽입되어야 하는 정렬된 배열 arr에서 요소의 위치를 찾는 bisect 모듈의 bisect_left() 함수를 호출합니다. 요소가 배열에 이미 존재하는 경우 이 함수는 해당 위치를 반환합니다.
그런 다음 함수는 반환된 인덱스 i가 배열 범위 내에 있는지, 해당 인덱스의 요소가 x와 같은지 확인합니다.
조건이 true이면 함수는 인덱스 i를 배열의 요소 위치로 반환합니다.
조건이 false이면 함수는 해당 요소가 배열에 없음을 나타내는 -1을 반환합니다.
그런 다음 코드는 검색할 배열 arr과 요소 x를 정의합니다.
bin_search_bisect() 함수는 arr 및 x를 입력으로 사용하여 호출되고 반환된 결과는 결과 변수에 저장됩니다.
그런 다음 코드는 결과가 -1이 아닌지 확인하여 해당 요소가 배열에 있음을 나타냅니다. true인 경우 배열의 요소 위치를 인쇄합니다.
결과가 -1이면 코드는 해당 요소가 배열에 없다는 메시지를 인쇄합니다.

파이썬3

import> bisect> > def> binary_search_bisect(arr, x):> > i> => bisect.bisect_left(arr, x)> > if> i !> => len> (arr)> and> arr[i]> => => x:> > return> i> > else> :> > return> -> 1> > > # Test array> arr> => [> 2> ,> 3> ,> 4> ,> 10> ,> 40> ]> x> => 10> > # Function call> result> => binary_search_bisect(arr, x)> > if> result !> => -> 1> :> > print> (> 'Element is present at index'> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )>

산출