배열 A에 오름차순으로 저장된 데이터를 이진탐색(binary searc… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 09년 1회차
배열 A에 오름차순으로 저장된 데이터를 이진탐색(binary search)하기 위하여 반복적(iterative) 알고리즘을 이용하여 기술하였다. ㉠, ㉡에 들어갈 적당한 명령은?
procedure BINARYSEARCH(A, n, x, j)
lower ← 1 ; upper ← n ;
while lower ≤ upper do
mid ← the middle element;
case
: x > A(mid):    ㉠   ;
: x < A(mid):    ㉡   ;
: else : j ← mid ; return;
end
end
j ← 0 ;
end
1
lower ← mid + 1 / upper ← mid - 1
2
upper ← mid + 1 / lower ← mid - 1
3
lower ← mid - 1 / upper ← mid + 1
4
upper ← mid - 1 / lower ← mid + 1
해설

㉠은 lower ← mid + 1, ㉡은 upper ← mid - 1이다.

x가 A(mid)보다 크면 찾는 값은 mid 오른쪽에 있으므로 하한을 mid 다음으로 올리고, 작으면 왼쪽에 있으므로 상한을 mid 앞으로 내린다. mid는 이미 비교했으므로 ±1로 제외해야 구간이 줄어 반복이 끝난다.

  • upper ← mid + 1 / lower ← mid - 1: x가 클 때 상한을 건드려 왼쪽 구간을 남기므로 찾는 값을 놓친다.
  • lower ← mid - 1 / upper ← mid + 1: 갱신할 변수는 맞지만 ±1 방향이 반대라 mid가 구간에 다시 포함되므로, lower와 upper가 같아진 뒤에도 구간이 줄지 않아 반복이 끝나지 않을 수 있다.
  • upper ← mid - 1 / lower ← mid + 1: x가 클 때 오른쪽이 아닌 왼쪽 구간을 남겨 찾는 값을 놓친다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 09년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기