[4.16] 문제 12. 이분 탐색 Binary search

문제 12. 이분 탐색

 

이분 탐색은 찾는 값을 향한 '방향'으로만 탐색하는 것이다.

입력 리스트는 이미 정렬되어 있음.

 

알고리즘 생각중..

입력 : (리스트, 찾는 값)

새로 정의 : (리스트, 찾는 값, i)

0. 종료 조건

- len 리스트 == 1 ?

1. 중간 위치 도출해서 값을 비교한다. 

- mid = len(a) // 2

- i = mid

- 중간값 = 찾는 값이면 -> return mid

- 중간값 < 찾는 값이면 -> 재귀함수 [:중간값]

- 중간값 > 찾는 값이면 -> 재귀함수 [중간값:]

값 말고 위치를 기억해야 한다. 그래서 return i를 해야함. 

이렇게 끄적끄적 적고 만들어봐도 절대 혼자 못한다. 

첨엔 걍 예시코드 봐야함. 

 

이분 탐색 알고리즘

def binary_search(a, x):
  start = 0
  end = len(a) -1

  while start <= end:
    mid = (start + end) // 2
    if x == a[mid]:
      return mid
    elif x > a[mid]: 
      start = mid + 1
    else: 
      end = mid - 1
  return -1

#입력 리스트는 정렬되어 있어야 함.
a = [1, 2, 3, 4, 5, 6]
print(binary_search(a, 4))

def binary_search(a, x):
  #start, end를 기준으로 잡음
  #while문 아래서 범위를 좁혀간다. 
  start = 0
  end = len(a) -1

  while start <= end:
    mid = (start + end) // 2
    if x == a[mid]:
      return mid
    elif x > a[mid]: #[a[mid]], x]
      start = mid + 1
      #start를 키워서 다시 탐색한다. 
    else: 
      end = mid - 1#[x,a[mid]]]
      #end를 줄여서 다시 탐색한다. 

  return -1
  #끝까지 해도 x 없으면 -1

d = [1,2,3,4,5]
print(binary_search(d, 1))

재귀함수 이분탐색 알고리즘 - 연습문제 

오 풀었다

def binary(a, x, start, end):
  mid = (start + end) // 2
  if x == a[mid]:
    return mid
  elif x > a[mid]:
    return binary(a, x, mid +1, end)
  else:
    return binary(a, x, start, mid-1)

def binary_search(a, x):
  return binary(a, x, 0, len(a) -1)


a = [1, 2, 3, 4, 5, 6]
print(binary_search(a, 1))