한국어
메뉴

자료 구조와 알고리즘

배열 가운데의 원소와 비교하여 찾는 범위를 절반씩 좁혀 가는 이진 탐색을 사용하기 위한 전제 조건으로 올바른 것은?

  1. A데이터의 개수가 2의 거듭제곱일 것
  2. B데이터가 키 순서로 정렬되어 있을 것
  3. C데이터에 같은 값이 포함되어 있지 않을 것
정답과 해설 보기

정답: B. 데이터가 키 순서로 정렬되어 있을 것

이진 탐색은 가운데 원소와 비교한 결과로 목표 값이 앞쪽 절반과 뒤쪽 절반 중 어디에 있는지를 정하여 범위를 절반으로 줄입니다. 이는 데이터가 정렬되어 있기 때문에 할 수 있는 판단이며, 정렬되어 있지 않은 배열에는 사용할 수 없습니다. 데이터의 개수가 2의 거듭제곱이 아니어도, 가운데 위치를 (하한 + 상한) ÷ 2의 버림 등으로 정하면 문제없이 동작합니다. 같은 값이 포함되어 있어도 탐색은 가능하며, 그 값 중 어느 하나가 발견됩니다(첫 위치를 구하려면 약간의 궁리가 필요합니다).

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 오름차순으로 정렬된 서로 다른 1,000개의 값에서 이진 탐색으로 값을 찾는다. 1회의 비교로 '일치·더 작다·더 크다'를 알 수 있다고 하면, 찾는 경우와 찾지 못하는 경우를 모두 포함하여 비교 횟수는 최대 몇 회인가?
  2. 오름차순으로 늘어선 배열 a[0]~a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60에서 이진 탐색으로 38을 찾는다. 찾는 범위를 하한 lo = 0, 상한 hi = 9에서 시작하고, 가운데 위치를 (lo + hi) ÷ 2의 버림으로 한다. 38과 비교되는 원소의 값을 차례로 나열한 것은?
  3. 배열 5, 3, 8, 1, 4를 버블 정렬로 오름차순 정렬한다. 앞에서부터 이웃한 원소끼리 비교하여 왼쪽이 더 크면 교환하는 조작을 끝까지 1회 수행한(1패스) 후의 배열은?
  4. 배열 29, 10, 14, 37, 13을 선택 정렬(정렬되지 않은 부분에서 최솟값을 찾아, 정렬되지 않은 부분의 맨 앞과 교환한다)로 오름차순 정렬한다. 이 조작을 2회 수행한 후의 배열은?
  5. 원소 수 10인 배열을 삽입 정렬로 오름차순 정렬한다. 두 번째 이후의 원소를 차례로 꺼내어, 왼쪽 이웃부터 차례로 비교하며 꺼낸 값 이하인 원소가 발견되거나 맨 앞에 도달할 때까지 비교한다. 처음부터 오름차순으로 늘어서 있는 경우와 내림차순으로 늘어서 있는 경우의 비교 횟수의 조합은?