반에서 제일 키가 큰 친구를 컴퓨터가 찾으려면 각각의 a와b의 친구의 키를 비교한 후에 더 큰 쪽을 남기고 그친구를 다시c와 비교하고... 반복하는 식으로 찾을수 있을것이다. 이 방법을 선형 검색이라고 한다. 각각의 요소를 전부 비교해서 원하는 값을 찾는 방법이다.
10억개의 전화번호가 있는 전화번호부에서 특정한 사람의 전화번호를 찾으려면,
첫장부터 찾는 사람은 없을것이다 전화번호부를 반으로 펴서 펼친 페이지보다 이름이 뒤면 뒤로가고 앞이면 다시 앞으로가고
남은 반의 부분에서 또 반을 펼쳐서 다시 반복하는식으로 찾으면서 찾을것이다.
이러한 방식을 이진 검색이라고 한다 절반을 찍어놓고 나머지 반을 버리기 때문에 과정마다 작업량이 두배로 줄어든다
이러한 방식으로 10억개의 전화번호부에서 찾을때는 10억이 약 2^30 이기 때문에 30번만 검색을 하면 된다.
>_<