[Algorithm] 이진 탐색 (Binary Search) : 과정 및 예제 코드

2021. 9. 4. 05:24·Computer Science/Algorithm
728x90

 

이진 탐색 (Binary Search)

데이터가 정렬되어 있어야만 사용할 수 있으며, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하며 원하는 데이터를 찾는 과정

 

 

 

 

Steps : 정렬된 10개의 데이터 중 값이 4인 원소 이진 탐색

 

 

 

 

시간 복잡도

- 시간 복잡도 : O(logN)

- 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점

 

- 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘아가면 이진 탐색과 같이 O(logN)의 속도를 내는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다

- 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해보자

 

 

 

 

Code with Python

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

def binary_search_recursive(array, target, start, end):
    if start > end:
        return None

    mid = (start + end) // 2

    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search_recursive(array, target, start, mid - 1)
    else:
        return binary_search_recursive(array, target, mid + 1, end)

 

2. 반복문으로 구현한 이진 탐색 

def binary_search_iter(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

 

 

 

 

 

 

 

 

📚 참고서적 : 이것이 코딩테스트다 with 파이썬

 

 

728x90
저작자표시 비영리 (새창열림)

'Computer Science > Algorithm' 카테고리의 다른 글

[Algorithm] 최단 경로 알고리즘 : 다익스트라(Dijkstra), 플로이드 워셜(Floyd-Warshall) 알고리즘 파이썬 예제 코드  (0) 2021.09.04
[Algorithm] 다이나믹 프로그래밍(Dynamic Programming) : 메모이제이션(Memoization), 탑다운(top-down) / 보텀업(bottom-up)  (0) 2021.09.04
[Algorithm] 정렬 (Sorting) : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 파이썬 정렬 라이브러리 예제 코드 및 시간 복잡도  (0) 2021.09.04
[Algorithm] DFS (깊이 우선 탐색) / BFS (너비 우선 탐색) : 파이썬 예제 코드 + 인접 행렬, 인접 리스트  (0) 2021.09.01
[Algorithm] 파이썬에서 스택(Stack)과 큐(Queue)의 사용  (0) 2021.09.01
'Computer Science/Algorithm' 카테고리의 다른 글
  • [Algorithm] 최단 경로 알고리즘 : 다익스트라(Dijkstra), 플로이드 워셜(Floyd-Warshall) 알고리즘 파이썬 예제 코드
  • [Algorithm] 다이나믹 프로그래밍(Dynamic Programming) : 메모이제이션(Memoization), 탑다운(top-down) / 보텀업(bottom-up)
  • [Algorithm] 정렬 (Sorting) : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 파이썬 정렬 라이브러리 예제 코드 및 시간 복잡도
  • [Algorithm] DFS (깊이 우선 탐색) / BFS (너비 우선 탐색) : 파이썬 예제 코드 + 인접 행렬, 인접 리스트
s_ih_yun
s_ih_yun
  • s_ih_yun
    CODESYUN
    s_ih_yun
  • 전체
    오늘
    어제
    • 분류 전체보기 (339) N
      • Web (8)
      • Java (7)
      • Spring (19) N
      • Git (16)
      • MyBatis (1)
      • HTML & CSS (14)
      • JavaScript (11)
      • DevOps (4)
      • Cloud (8)
      • Lanuage (13)
        • C++ (3)
        • Python (10)
      • DB (1)
        • MySQL (1)
        • Oracle (2)
      • Computer Science (26)
        • Concept (3)
        • Algorithm (23)
      • Baekjoon (104)
        • 단계별로 풀어보기 (78)
      • CodeUp (98)
        • Python 기초 100제 (98)
      • Programmers (2)
      • Books (3)
      • etc (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

    • Syun's Pages
  • 인기 글

  • 태그

    git
    C
    Tistory
    자료구조
    CodeUp 기초 100제
    웹
    clean code
    codeup
    c++
    Cloud
    SourceTree
    web
    Programmers
    BOJ
    단계별로 풀어보기
    myBatis
    aws
    HTML
    JavaScript
    CSS
    java
    Python
    알고리즘
    oracle
    spring
    VS Code
    MySQL
    db
    github
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
s_ih_yun
[Algorithm] 이진 탐색 (Binary Search) : 과정 및 예제 코드
상단으로

티스토리툴바