탐색 알고리즘

선형 탐색 알고리즘

컴퓨터에 저장된 데이터 집합에서 어떤 조건이나 성질을 만족하는 데이터를 찾는것이다.

탐색하고자 하는 데이터는 무작위로 섞여있는 데이터와 특정한 규칙에 따라 정렬된 데이터로 구분할 수 있다.

데이터의 유형에 따라 적합한 탐색 방법이 있는데, 우선 무작위로 섞여있는 데이터를 탐색하는 방법인 선형 탐색에 대해 살펴보자.

선형 탐색은 순차 탐색이라고도 하는데, 주어진 데이터 집합에서 원하는 데이터를 처음부터 순차적으로 비교하면서 찾는 방법이다.

다음 데이터 집합에서 선형 탐색을 이용해서 데이터 7을 탐색하는 과정을 알아보자.

① 첫 번째 데이터인 15와 7을 비교한다. 값이 다르므로 다음으로 이동한다.

② 두 번째 데이터인 19와 7을 비교하는데, 다르므로 다음으로 이동한다.

③ 세 번째 데이터인 5와 7을 비교하는데, 다르므로 다음으로 이동한다.

④ 네 번째 데이터인 7과 찾고자 하는 3이 같으므로 원하는 데이터를 찾고 탐색을 종료한다.

만약 마지막까지 찾는 데이터가 없으면 탐색 실패를 알려주고 끝내야 한다.

임의의 숫자를 10개를 요소로 가지는 리스트를 만들고, 키 값을 입력했을 때 인덱스를 찾아 출력하는 선형 탐색 알고리즘을 구현하라.

분석

설계 (순서도)

구현

이진 탐색은 정렬된 데이터 집합을 이분화하면서 탐색하는 방법이다.
① 다음 데이터 집합에서 이진 탐색을 이용해서 데이터 9를 탐색하는 과정을 알아보자.

② 중간에 위치한 데이터인 7과 9를 비교한다.

③ 중간에 위치한 데이터인 7보다 찾고자 하는 데이터인 9가 크므로 7보다 오른쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다. 새로운 탐색 영역의 중간에 위치한 11과 9를 비교한다.

④ 11보다 9가 작으므로 11보다 왼쪽에 위치한 데이터들에 대해 다시 한번 이진 탐색을 수행한다. 새로운 탐색 영역의 중간에 위치한 9와 9를 비교한다. 찾고자 하는 데이터이므로 탐색을 종료한다.

⑤ 마찬가지로 마지막까지 찾는 데이터가 없으면 탐색 실패로 끝낸다.

임의의 숫자를 10개를 요소 또는 예시(a = [11, 18, 26, 27, 39, 57, 63, 75, 76, 80])와 같은 리스트를 만들고, 키 값을 입력했을 때 인덱스를 찾아 출력하는이진 탐색 알고리즘을 구현하세요.

분석

설계 (순서도)

구현

마지막 ③인데 오타........ 하.........