리스트의 중간 값을 찾아 원하는 값과 비교해서 진행하는 알고리즘이다.
이 알고리즘을 이용하려면 먼저 정렬이 되어있어야한다.
중간값 = (최솟값 + 최댓값) / 2
중간값 위치에 해당하는 값과 검색하고자 하는 값과 비교한다. 만약 찾고자 하는 값이 중간 값보다 크다면 중간 값 이하는 검색하지 않고, 작다면 중간 값 이상은 검색하지 않는다.
이렇게 원하는 값 찾을 때까지 검색 범위를 반씩 쪼개며 찾는다.
이분 검색의 시간 복잡도는O(logN)이다.
아래는 예시 문제 및 풀이코드다.
[인프런] Node.js / 섹션7-정렬과 그리디, 결정알고리즘 / 10. 이분검색
문제 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로
sanghee01.tistory.com
'CS > Data structure & Algorithom' 카테고리의 다른 글
| 단순 연결 리스트(Singly Linked List) (0) | 2023.06.18 |
|---|---|
| 선택 정렬, 버블 정렬, 삽입 정렬 (0) | 2023.02.19 |
| 스택(Stack), 큐(QUEUE) (0) | 2023.02.08 |
| 슬라이딩 윈도우(Sliding Window) 알고리즘 (0) | 2023.02.03 |
| 투 포인터(Two Pointers) 알고리즘 (0) | 2023.01.31 |