JAVA_코딩테스트 준비_이진 탐색 알고리즘 (Binary Search Algorithm)

이진 탐색 알고리즘 (Binary Search Algorithm)

우리가 특정 값을 찾을 때 자료를 확인해서 특정 값에 도달하는것을 탐색이라고 한다. 

만약 임의의 숫자를 지정해 놓고 찾으라고 한다면, 0부터 1, 2, 3..... 순으로 계속 확인 한다고 하자

이 경우 통상적인 숫자 (적당한 숫자, 100 이하라고 하자) 인 경우 금방 답이 나오겠지만, 높은 숫자 (100000....)의 경우에는 굉장히 오랜 시간이 걸릴 것이다. 

탐색 알고리즘은 특정 값을 찾는데 걸리는 시간을 줄이면서 우리가 원하는 값을 내놓기 위해 만들어졌다.

이진 탐색 알고리즘은 앞에서 예를 든 숫자 업다운 과 동일하다고 보면 된다.

만약 5~200까지 숫자 중 182를 찾는 경우라고 생각해 보자 

5~200범위의  이진탐색 예시 (출처 : 코드스테이츠)

위의 그림에서 5~200 범위의 숫자 중 182의 숫자를 찾아내는 예시이다. (그림의 간략화를 위해 중간수는 많이 생략)

1. 마치 업 다운 게임을 하는 것 처럼 찾고자 하는 범위를 반으로 나누어서 내가 차는 숫자보다 낮으면  제외시킨다
   -> 탐색범위를 반으로 줄임
   
   
2. 또 남은 범위에서 중간값 기준으로 내가 찾아햐 하는 숫자보다 적은 범위는 제외
   -> 또또 탐색범위를 반으로 줄임 
   
3. 이를 반복해서 중앙값이 182로 딱 떨어지거나, 숫자가 2개 남는 순간 찾고자 하는 값이 나오게 된다.

결국 연산할수록 범위가 계속 줄어들기 때문에 O(log n)의 시간복잡도를 가지는 알고리즘이 된다.

이진탐색은 생각보다 많은 곳에 사용된다고 한다.

• 사전 탐색 : 사전에서 단어 찾을때 
  
  
• 도서관 장서 검색 : 도서 청구기호로 책 찾을때 
  
  
• 대규모  시스템에 대한 리소스 사항 파악 : 시스템 부하 테스트에서 예측된 부하를 처리하는데 필요한 CPU양을 파악할때 사용
  
  
• ADC : 아날로그 신호값을 디지털로 만들 때 사용