-
이진탐색과 순차탐색
-
Zappy (IP: *.51.113.11)조회 수: 10543, 2007-03-21 23:53:05(2007-03-21)
-
★ 질문
다음과 같은 10개의 리스트 L ={ 1, 23, 4, 5, 15, 17, 8, 30, 11, 13} 이 있을 때
x= 6을 리스트에서 찾는 방법을 이용하여 순차탐색방법과 이진탐색방법을 설명해 주세요?반갑습니다.....
거두절미하고.....
말씀하신 순차탐색(Sequential Searching혹은 Linear Searching)과 이진탐색
(혹은 이분탐색 Binary Searching)은 탐색의 방법중 가장 흔히 사용하는
방법중의 하나입니다.....
먼저 순차탐색은 말그대로 앞에서부터 차례차례 찾아나가는 방법을 말합니다..
위의 리스트라면 맨앞 1부터 23, 4......이런순서로 하나하나 x=6인가를
비교해 나가는 검색을 말합니다......물론 리스트가 끝인지 아닌지의 검색도
당연히 병행해야겠지요....
그다음 이진 탐색은 먼저 리스트의 원소들이 키(key)에 의해 정리되어 있어야
한다는 조건이 있습니다....
위의 리스트를 정리해보면 L = {1,4,5,8,11,13,15,17,23,30}로 정리가 되며
여기서 중간의 값 11과 x=6을 비교하고 일치하지 않으므로, x=6 < 11이므로
다시 순서에서의 중간값 즉 5와 x=6을 비교하고, 여기서도 일치하지 않으므로
그다음의 중간값 8과 비교하는.........그런 방식입니다.....
Binary Searching의 장점이라면 검색시마다 리스트가 탐색의 대상이 반으로
줄어든다는 장점이 있지만 말씀드린거처럼 원소들이 키(key)에 의해 정리되어 있어야
한다는 조건을 가지고 있기도 합니다...
도움이 되었길 바랍니다....
| 번호 | 제목 | 닉네임 | 조회 | 등록일 |
|---|---|---|---|---|
| 22 |
![[레벨:18]](http://zappygo.com/modules/point/icons/default/18.gif "포인트:32300point (94%), 레벨:18/30"){kind=icon} Zappy | 25176 | 2010-05-09 | |
| 21 | Zappy | 12417 | 2007-03-25 | |
| 20 | Zappy | 6070 | 2007-03-21 | |
| ⇒ | Zappy | 10543 | 2007-03-21 | |
| 18 | Zappy | 7956 | 2006-10-25 | |
| 17 | Zappy | 9143 | 2006-10-25 | |
| 16 | Zappy | 12227 | 2006-10-25 | |
| 15 | Zappy | 7916 | 2006-10-25 | |
| 14 | Zappy | 60144 | 2006-10-25 | |
| 13 | Zappy | 9221 | 2006-10-25 |
