이진 검색을 위한 Python 프로그램

이 기사에서는 주어진 문제 설명을 해결하기 위한 솔루션과 접근 방식에 대해 알아볼 것입니다.

문제 설명 - 정렬된 목록이 제공되며 이진 검색을 통해 요소를 찾아야 합니다.

알고리즘

• x를 중간 요소와 비교하십시오.

• x가 중간 요소와 일치하면 중간 인덱스를 반환합니다.

• 그렇지 않으면 x가 중간 요소보다 크면 x는 중간 요소 뒤의 오른쪽 절반 하위 배열에만 있을 수 있습니다. 따라서 오른쪽 절반에 대해 반복됩니다.

• 그렇지 않으면(x는 더 작음) 왼쪽 절반에 대해 반복됩니다.

재귀 알고리즘

예시

def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
   mid = start + (end- start)//2
   # If element is present at the middle
   if arr[mid] == x:
      return mid
   # If element is smaller than mid
   elif arr[mid] > x:
      return binarySearchAppr(arr, start, mid-1, x)
   # Else the element greator than mid
   else:
      return binarySearchAppr(arr, mid+1, end, x)
   else:
   # Element is not found in the array
      return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
x ='r'
result = binarySearchAppr(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")

반복 알고리즘

예시

def binarySearchAppr (arr, start, end, x):
# check condition
   if end >= start:
      mid = start + (end- start)//2
      # If element is present at the middle
      if arr[mid] == x:
      return mid
      # If element is smaller than mid
      elif arr[mid] > x:
      return binarySearchAppr(arr, start, mid-1, x)
      # Else the element greator than mid
      else:
      return binarySearchAppr(arr, mid+1, end, x)
   else:
      # Element is not found in the array
      return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
   x ='r'
   result = binarySearchAppr(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 4

결론

이 기사에서는 이진 검색을 적용하는 접근 방식에 대해 배웠습니다.