[Theory] Search

25 Feb 2022

탐색(Search)

탐색알고리즘은 내가 가지고 있는 데이터 중 원하는 값의 데이터를 찾고자 할때 사용되는 알고리즘으로 대표적인 예시로 선형 탐색 (linear Search), 이진 탐색 (Binary Search), 해시 탐색 (Hash Search)이 있다.

이중 오늘은 선형 탐색과 이진탐색에 대해 간단하게 설명 하고자 한다.

선형 탐색법 (linear Search)

선형 탐색법은 왼쪽에서 오른쪽으로 또는 오른쪽에서 왼쪽으로 순서대로 하나하나 찾는 탐색 알고리즘이다.

• 먼저 H라는 값을 찾고자 한다면 왼쪽 값 부터 시작해서 오른쪽으로 하나하나 값을 탐색한다.

• H라는 값을 찾을 경우 해당 값에서 탐색을 종료한다.

이진 탐색법 (Binary Search)

이진 탐색법은 중간 지점(중간값)을 선택 한 후, 왼쪽이나 오른쪽만 남긴뒤 이를 반복해서 탐색하는 알고리즘이다.

• A라는 값을 찾을 경우 먼저 중간값 G를 선택 후 방향을 골라 해당 값 만을 남긴다.

• 방향은 왼쪽을 선택했으므로 오른쪽값은 버리고 또 남은 왼쪽값들의 중간 지점을 선택한다.

• 이후 해당 방법을 반복해서 값을 찾아낸다.

구현

선형 탐색법

이진 탐색법