정화 코딩

이진 탐색 (Binary Search) 본문

Data Structure & Algorithm

이진 탐색 (Binary Search)

jungh150c 2023. 9. 4. 15:19

탐색 (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

 

Comments