[Algorithm] 이분 탐색 / 이진 탐색 (Binary Search) 알고리즘

🌵이분 탐색(Binary Search) 이란?

 

- 정렬되어 있는 리스트(배열)에서 탐색 범위를 절반씩 좁혀가며 원하는 값(target)을 탐색하는 방법
- 이 때 리스트(배열)는 항상 정렬되어 있어야 한다

시간 복잡도 : O(log n)

 

---

 

 

🌵문제 해결 방법

 

이분 탐색 알고리즘은 변수 3개 (start, mid, end)를 사용해 값을 탐색

간단하게 말하면 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이분 탐색의 과정 

 

변수 이름에서도 알 수 있듯,

start의 초기 값은 리스트(배열) 시작 위치 (0)
mid 는 start와 end의 중간 지점 ((start + end) // 2)
end 는 리스트(배열) 마지막 위치 (len(list) - 1)

 

 

1. 리스트(배열)의 중간 값(mid)을 선택해 찾고자 하는 값과 같은지 확인
2. 만약 찾고자 하는 값이라면 해당 값을 반환
3. 만약 (중간 값이) 찾고자 하는 값보다 작다면 (mid < target), 
    검사 범위를 큰 쪽으로 이동 -> start = mid + 1
4. 만약 찾고자 하는 값보다 크다면 (mid > target), 
    검사 범위를 작은 쪽으로 이동 -> end = mid + 1
5. 위의 과정을 반복하다가 원하는 값이 나오면 해당 값을 반환
6. 위의 과정을 반복하다가 더 이상 검사할 곳이 없을 경우 (start > end) 종료

 

 

---

 

 

🌵Python Code

 

1. 반복문을 사용한 코드

# 반복문 사용한 이진탐색 코드

def binary_search(array, target):

  start = 0
  end = len(array) - 1
  
  while start <= end:

    mid = (start + end) // 2
    # 원하는 값 찾은 경우 인덱스 반환
    if array[mid] == target:
      return mid

    # 원하는 값이 mid보다 작은 경우 왼쪽으로 범위 이동
    elif array[mid] > target:
      end = mid - 1

    # 원하는 값이 mid보다 큰 경우 오른쪽으로 범위 이동
    else:
      start = mid + 1

    return None

 

 

 

2. 재귀함수를 사용한 코드

# 재귀 함수로 구현한 이진 탐색

def binary_search(array, target, start, end):    
    if start > end:
        return None
    
    mid = (start + end) // 2

    # 원하는 값 찾은 경우 인덱스 반환
    if array[mid] == target:
        return mid
    
    # 원하는 값이 mid보다 작은 경우 왼쪽으로 범위 이동
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
        
    # 원하는 값이 mid보다 큰 경우 오른쪽으로 범위 이동
    else:
        return binary_search(array, target, mid + 1, end)

 

 

---

 

🌵 관련 문제

 

 

🥈[백준 알고리즘 1654번 : 랜선 자르기]

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

[SOLUTION]

https://gyurisinzorba.tistory.com/54

[Python] 백준 알고리즘 1654번 : 랜선 자르기

 

 

---

🥈[백준 알고리즘 2805번 : 나무 자르기]

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

[SOLUTION]

https://gyurisinzorba.tistory.com/56

[Python] 백준 알고리즘 2805번 : 나무 자르기

---

🥈[백준 알고리즘 2776번 : 암기왕]

https://www.acmicpc.net/problem/2776

2776번: 암기왕

[SOLUTION]

https://gyurisinzorba.tistory.com/55

[Python] 백준 알고리즘 2776번 : 암기왕

---

 

~ 해당 포스팅은 업데이트 중 ~