이진탐색
1.이진탐색이란?
정렬된 데이터 집합을 이분화하면서 탐색하는 방법[1]이다.
2.정리
우리는 독서할때 특정 페이지를 열람하기 위해서 1페이지부터 차례대로 넘길까? 아니다 1페이지부터 차례대로 책을 넘기지않고 원하는 페이지가 100페이지라면 100페이지 근처라고 생각되는 페이지를 열어본다.
컴퓨터도 마찬가지다. 1부터 100까지 차례대로 접근하는게 아니라 어느정도 비슷한 위치부터 시작해서 고려 범위를 줄이는 방법이 좋지 않을까? 이것이 바로 이진탐색이다.
3.구상
이진탐색은 고려해볼 사항이 많다. 탐색되는 데이터가 어떤 데이터 리스트인가? 데이터 리스트는 정렬이 되어있는가? 정렬이 되어 있지 않는다면 정렬이라는 시간도 고려해봐야한다. 즉 정렬된 데이터 리스트에서 탐색일때 굉장히 유용한 탐색 알고리즘이 될것 같다. 이번 구현은 아래와 같은 가정으로 구현하려 한다.
선택한 유저의 정보를 찾는 프로그램, 유저 정보는 id 순서대로 정렬되어있다. 이진탐색으로 구현해보아라.
-클래스 다이어그램
-뇌피셜
0. User라는 객체의 리스트 10개가 정렬되어 존재할때 이 리스트에서 id가 3인 데이터를 찾는다.
1. left 변수는 가장 처음인 0 값으로 초기화 한다.
2. right 변수는 배열의 마지막 값으로 초기화 한다. right=LIST_SIZE 또는 right = sizeof(user_list)/sizeof(user_list[0])
3. pivot 변수는 주어진 리스트의 중간 값으로 초기화 한다. pivot = LIST_SIZE/2
4. pivot 위치에 있는 id값과 찾고 싶은 값인 id값(3)과 비교한다.
5. 만약 pivot이 id값보다 크다면
5.1 찾고 싶은 값은 그 아래에 있다는 것이므로 left변수는 고정한다.
5.2 이분할 새로운 기준이 필요하기 때문에 pivot의 위치를 right가 위치하게된다. right=pivot
5.3 이제 새로 구성된 left와 right 값으로 pivot의 위치를 설정한다. (left+right) / 2
5.4 새로 구한 pivot의 id값과 검색 id값을 비교한다..
6. 만약 pivot이 id 값보다 작다면
6.1 찾고 싶은 값은 그 위에 있다는 것이므로 right 변수는 고정한다.
6.2 이분할 새로운 기준이 필요하기 때문에 left의 위치를 pivot위치로 설정한다. left = pivot
6.3 이제 새로 구성된 left와 right 값으로 pivot의 위치를 재설정 한다. (left+right) /2
6.4 새로 설정한 pivot의 id값과 검색id값을 비교한다..
7. 5~6번 작업을 반복하면서 리스트를 모두 탐색한다.
4.검증
5.구현
GITHUB : https://github.com/gelos12/algorithm/tree/master/01.BinarySearch
6.후기
7.참고
[1] 네이버 지식백과 : 이진탐색