이진 탐색(Binary Search)
정렬되어 있는 데이터에서 특정한 값을 찾아내는 알고리즘
** Binary : 하나를 두개로 쪼개는 것을 뜻함
> 이진 탐색(Binary Search) 특징
- 검색 관련된 작업 수행(Search Algorithm)
- 선형 검색의 발전된 방법
- 배열이 순서대로 정렬되어 있는 상태라면 O(logN)의 시간 복잡도로 문제 해결 가능
| 이진 탐색 동작방식
- 배열의 중간값을 찾아서 내가 찾고자 하는 값이 중간값인지 확인(이진 탐색은 중간에서 시작)
- 중간값이 아닐경우 내가 찾고자 하는 값이 중간값보다 작은 경우 왼쪽으로 이동
- 중간값이 아닐경우 내가 찾고자 하는 값이 중간값보다 큰 경우 오른쪽으로 이동
| 장점
- 정렬되 배열에서 검색은 정렬이 안된 경우보다 정말 빠름
- 데이터가 2배가 되어도 절차/스텝은 +n개임
- 10개 데이터에서 3번만에 찾았다면 20개 데이터에서 4번만에 찾을 수 있음
| 단점
- 정렬된 배열에 아이템을 추가하는 것은 정렬이 안된 경우보다 시간이 더 걸림
> 선형 탐색(Linear Search) 특징
- 검색 관련된 작업 수행(Search Algorithm)
- 검색을 하기 위한 '자연스러운' 방법
- 배열의 처음부터 끝까지 하나씩 검색
- 최악의 경우 내가 찾고자 하는 값이 배열의 맨 마지막에 존재, 배열에 아예 없는 경우
| 단점
- 배열이 커지면 커질수록 선형검색을 하는 시간이 길어짐(선형 시간복잡도 O(N))
> 시간복잡도(Time Complexity)
- 얼마나 많은 절차/스텝이 필요한지?
- 적은 절차로 같은 작업을 수행하는 알고리즘이 더 훌륭한 알고리즘임
참고
