정화 코딩
이진 탐색 (Binary Search) 본문
탐색 (Search)
여러 데이터들 중에서 원하는 값을 찾는 알고리즘
1. 순차 탐색 (Linear Search)
💡 정의
리스트의 항목들을 처음부터 마지막까지 하나씩 순서대로 검사하는 알고리즘
💡 과정
1️. 맨 앞 데이터와 찾으려는 데이터가 같은지 비교한다.
2️. 다르다면 다음 데이터와 찾으려는 데이터가 같은지 비교한다.
3. 같은 데이터를 찾기 전까지 2의 과정을 반복하고, 같은 데이터를 찾으면 종료한다.
💡 특징
- 정렬되지 않은 리스트에도 적용 가능하다.
- 시간복잡도: O(n)
2. 이진 탐색 (Binary Search)
💡 정의
배열을 반으로 쪼개어 찾으려는 값이 왼쪽에 있는지 오른쪽에 있는지를 찾아 탐색 범위를 좁혀가며 탐색을 진행하는 알고리즘
💡 과정
1️. 시작 인덱스와 마지막 인덱스 사이의 중간 값에서 소수점 이하를 버려 중간 인덱스를 정한다.
2️. 중간 인덱스에 해당하는 데이터와 현재 찾으려는 데이터가 같은지 비교한다.
3️. 중간 값이 더 크면 중간 인덱스 이후의 값은 확인하지 않고, 마지막 인덱스를 중간 인덱스로부터 한 칸 앞으로 옮긴다. 반대로, 중간 값이 더 작다면 시작 인덱스를 중간 인덱스로부터 한 칸 뒤로 옮긴다.
4️. 중간 인덱스의 값과 찾으려는 값이 같아질 때까지 2️의 과정과 3️의 과정을 반복한다.
💡 특징
- 배열이 반드시 오름차순으로 정렬되어 있어야 한다.
- 추가되거나 삭제되지 않고 변하지 않는 고정된 데이터에서 탐색을 해야할 때 유용하다.
- 시간복잡도: O(logN)
[출처 및 참고]
https://woodforest.tistory.com/32
https://heytech.tistory.com/64
https://kangdy25.tistory.com/107
'Data Structure & Algorithm' 카테고리의 다른 글
[컴퓨터알고리즘] LCS 알고리즘 구현 (0) | 2024.05.06 |
---|---|
파이썬으로 이진 탐색 구현 (0) | 2023.09.05 |
파이썬으로 스택, 큐, 덱 구현 (0) | 2023.08.25 |
정렬 (Sorting) (0) | 2023.01.18 |
스택, 큐, 덱 (Stack, Queue, Deque) (0) | 2023.01.09 |