선택정렬 이진탐색
- 최초 등록일
- 2011.12.24
- 최종 저작일
- 2011.09
- 8페이지/ 한컴오피스
- 가격 1,500원
소개글
n개의 정수를 입력받아 선택정렬을 통해 순서대로 정렬하여 출력하고 이 정수들중 찾고자 하는 정수를 찾아 찾았을 경우와 못 찾았을 경우를 출력합니다.
c언어와는 문법이 조금 다른 c++언어의 기초 문법을 적용하여 자료구조의 기초를 익히고 익숙해지며 최대한 함수를 많이 나누어 함수로 값을 전달하고 값을 바꾸는 것에도 익숙지는것이 이번 과제의 목적입니다.
목차
① 문제인식
② 문제분석 및 해결방법
③ 알고리즘
④ 소스(주석)
⑤ 결과화면
⑥ 느낀점
본문내용
<이진탐색>
이진탐색은 n>=1개의 서로 다른 정수가 이미 정렬되어 배열에 저장되어 있을때 x=a[j]인 x가 존재하면 j를 반환하고 그렇지 않으면 -1을 반환하여 정수를 찾았는지 몇 번째에서 찾았는지를 알수 있습니다.
첫째, left, right는 탐색하고자 하는 리스트의 중간위치 middle=(left + right)/2로 설정합니다.
둘째, a[middle]과 x를 비교할 경우 x가 a[middle]보다 작을 경우, 같을 경우 큰 경우 세가지 경우가 존재합니다.
ㄱ. x<a[middle] : x가 존재한다면 0과 middle -1 사이에 있으므로 right는 middle-1로 설정합니다.
ㄴ. x==a[middle] : x와 같다면 middle를 반환합니다.
ㄷ. x>a[middle] : x가 존재한다면 middle+1 과 n-1사이에 있으므로 left를 middle+1로 설 정합니다.
x가 발견되지 않고 검사할 정수가 아직 남아있다면 middle값을 다시 설정하고 탐색을 계속합니다. 검사할 정수가 아직 남아 있는지 결정하고 x를 a[middle]과 비교하는 두 작업을 계속하게 됩니다.
참고 자료
없음