[알고리즘] Binary Search란?

 * 이름이 붙여진 것처럼 Search하는 알고리즘인데, binary의 방법으로 진행한다.

  

     =>binary 방법이라는 것은 하나의 배열을 반으로 나누어서, 둘 중 한쪽을 선택하고, 또 반으로 나누고를 반복하는 방식이다.

 * 전제 조건

 => 정렬되어 있어야 한다.

* 과정

=> 정렬이 되어있다는 전제하에 진행한다.

(실제로 정렬이 되어있지 않다면, 정렬 후 진행해야 한다.)

1. 숫자 n을 찾는다고 가정 하였을 때, 중간 값 middle을 정한다.

2. middle보다 n이 크다면,  middle보다 큰 쪽을 본다.

3. middle보다 큰 쪽에서 1과 2를 반복적으로 진행하여, 숫자를 찾는다.

* 애니메이션 

http://www.cs.armstrong.edu/liang/animation/web/BinarySearch.html : 

* 시간 복잡도

숫자를 절반씩 지워나가면서 찾는다라는 것을 명심해보자.

그렇다는 것은 log n과 동일하다고 할 수 있다.

O(log n)!!!!!

ex) 1024개의 정렬된 배열이 존재할 때, binary search를 이용하면, 대략 10번이내에 찾을 수 있다.

* binary search의 효율성

-> 이미 배열이 정렬되어 있다면 binary search가 효율적임.

-> 숫자찾기를 엄청 많이 해야하는 경우에는 오히려 정렬을 한 뒤에 binary search를 하는 것이 좋다.

ex) 숫자가 100개가 있는데, 숫자 찾기를 1만번해야하는 경우...