[알고리즘] 탐색 알고리즘

이강일·2022년 6월 27일
0

선형 탐색(Linear Search)이란?

 
배열의 가장 처음부터 순차적으로 목표값에 도달할 때까지 목표값과 대조해가며 찾는 방식이다.

  • 검색법 중에 가장 단순하고 구현이 쉽고 어떤 배열에서든 사용이 가능하다는 장점이 있다.
  • 배열의 크기가 커지면 커질수록 소요시간 또한 길어지게 되는 단점이 있다.
  • 빅 오 표기법으로는 O(N)이다.

 

이진 탐색(Binary Search)이란?

 
오름차순으로 정렬된 배열에서 검색 범위를 반씩 줄여가며 목표값을 찾는 방식이다.

  • 선형 탐색보다 속도가 빠르다는 장점이 있다.
  • 정렬된 배열에서만 사용이 가능하다는 단점이 있다.
  • 빅 오 표기법으로는 O(log n)이다.

이렇게 정렬된 배열이 있다면

중간 지점을 찾는다.

목표값이 중간 지점의 값보다 큰지, 작은지를 비교한다.
크다면 기준(막대) 왼쪽을 제외, 작다면 기준(막대) 오른쪽을 제외한다.
이 과정을 반복해서 목표값을 찾아낸다.

0개의 댓글