[정보처리기사][알고리즘][자료구조] 이분검색 - 2차원 배열

Q. 키보드로 입력받은 번호에 대한 점수를 DATA 배열에서 찾아 출력하는 순서도를 작성하시오. 단, DATA(1,10) 배열에는 번호와 점수가 들어있다고 가정하고, 찾는 자료가 없을 경우 자료와 함께 Not Found를 출력하고 끝낸다.

1. 번호 순으로 정렬된 번호와 점수가 저장될 2차원 DATA배열을 선언한다. 자료가 저장되어있다고 가정한다.

 

2. 찾을 번호를 입력한다.

 

3. 검색 범위의 시작위치는 1이므로 L을 1로 초기화한다.

 

4. 검색 범위의 마지막 위치는 10이므로 H를 10으로 초기화한다. 10개의 열을 사용하므로 마지막 위치는 10이다.

 

5. 검색 진행 여부를 판단한다. 검색 범위의 시작 위치와 끝 위치를 비교하여 어떤 경우에 더 찾아봐야 하는지 생각한다.

 

1) 시작 위치가 더 크다면, 입력받은 값과 NOT FOUND를 출력하고 끝낸다.

 

2) 시작 위치가 작거나 같다면, 찾을 범위의 중간 위치를 계산한다.

 

3) 찾을 번호가 DATA(1,M)와 같으면 입력받은 번호를 찾은 것이므로 Yes로 가고 아니면 No로 간다.

 

A. Yes일 경우, 입력받은 번호 J, 찾은 점수 DATA(2,M)을 출력하고 끝낸다.

 

B. No일 경우, 입력받은 번호 J가 DATA(1,M)보다 작으면 중간 위치(M) 이전 범위에서 찾는 값이 있다는 것이므로 Yes로 가고 아니면 중간위치 이후 범위에 찾는 값이 있다는 것이므로 No로 간다.

 

A) Yes일 경우, 검색 범위의 마지막 위치를 중간 위치보다 1칸 이전으로 변경하고, 5번으로 간다.

 

B) No일 경우, 범위의 시작위치를 계산한다. 찾을 값 J가 중간위치의 값보다 큰 경우이므로 중간 값이 있는 위치의 다음 위치가 이제 찾을 범위의 시작 위치가 된다.

 

 

해당 글은 제가 만든 어플을 기준으로 작성하였습니다.

더많은 정보는 알고리즘 어플을 이용해주세요.