[알고리즘] 이진 탐색(Binary Search)
우선 탐색은 여러 정보들 중에서 특정한 값을 찾는 것이다. 사전을 예로 들어, 사전에서 특정한 단어를 찾는 방법은 대표적으로 2가지가 있다. Orange라는 단어를 찾는다고 해보자. 첫 번째 방법은 처음부터 Orange가 나올 때까지 찾아보는 것이다. 이 방법도 생각할 수 있다. 사전의 중간(Kiwi)을 펼쳐놓고 Orange의 위치는 이보다 뒤이므로 나머지 뒷부분에서 중간을 펼치고... 를 반복해 Orange를 찾는 방법이다. 첫번째 방법이 선형 탐색(순차 검색), 두번째 방법이 이진 탐색(이분 탐색)이라고 볼 수 있다. 선형 탐색(Linear Search) 처음부터 찾고자 하는 값이 나올 때까지 탐색하는 기법이다. 배열 [1, 2, 3, 4, 5, 6, 7, 8, 9] 이 있고 8을 찾는다고 하면, 선..