배열 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문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요비슷한 기출
- 자료흐름도(dataflowdiagram)의구성요소로옳은것은? {"answer":2,"content":[{"content":"process,dataflo20년-3회차-정보처리기사-필기
- 하향식통합에있어서모듈간의통합시험을위해일시적으로필요한조건만을가지고임시로제공되는시험용모듈을무엇이라고하는가? {"answer":1,"content":[{"c20년-1, 2회차-정보처리기사-필기
- 다음중가장강한응집도(cohesion)는? {"answer":1,"content":[{"content":"sequentialcohesion","url":21년-2회차-정보처리기사-필기