이진탐색(Binary_Search)

Binary_Search(이진 탐색)

1. Binary_Search란

---

배열의 내부 데이터가 정렬되어 있어야 사용가능한 알고리즘으로 조건만 맞다면 매우 빠르다. (O(logn)의 시간복잡도)

데이터를 절반씩 좁혀가므로 위치를 나타내는 변수 (시작점, 중간점, 끝점) 3개가 필요하다.

찾으려는 데이터와 중간점 위치의 데이터를 반복적으로 비교하는것이 진행방식이다.

---

2. 예시코드

---

2.1 재귀함수 방식

def binary_search(array, target, start, end):
  if start > end:     # array에 target값이 존재하지 않아 계속된 재귀함수 호출로 start > end가 된경우 None return
    return None
  mid = (start + end) // 2   # 중간점
  if array[mid] == target:    # mid값이 target인경우 - 찾은경우 종료
    return mid
  elif array[mid] > target:                               # mid값보다 target이 작은경우
    return binary_search(array, target, start, mid - 1)   # end값을 min - 1 로 바꾸어 탐색 범위를 반으로 줄인 재귀함수 호출
  else:
    return binary_search(array, target, mid + 1, end)     # target값이 mid값보다 큰경우, start 값을 mid + 1로 바꾸어 재귀함수 호출

---

2.2 단순 반복문을 활용한 방식

def binary_search(array, target, start, end):
  while start <= end:     # 반복하여 array == target일때까지 값을 찾음
    mid = (start + end) // 2

    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
    return None         # start > end 일때 None값 반환