이진 탐색 알고리즘

구글은 관련성이 높은 검색 결과를 정리해두고 원하는 정보를 찾도록 제시해준다.

우리가 구글에서 정보를 찾을 때 구글내부에선 어떤 동작이 일어날까?
어떤 필터링을 거쳐, 데이터를 어떻게 정렬하고, 우리에게 필요한 데이터만을 보여줄까?

데이터 정리하기: 정렬 알고리즘
데이터 검색하기: 탐색 알고리즘

먼저 살펴볼 것은 탐색알고리즘이다.

탐색알고리즘

탐색알고리즘의 종류는 크게 3가지가 있다.

• 선형 탐색 알고리즘
• 이진 탐색 알고리즘(Binary Search Algorithm)
• 해시 탐색 알고리즘

오늘은 이중에서 이진 탐색 알고리즘에 대해 알아볼 생각이다.

왜냐하면 시간복잡도로 계산할 때 O(log n) 에 해당하는 이 이진 탐색 알고리즘은 우리가 데이터를 검색할 때 최소시간대비 최대효율을 가져다주기 때문이다.

그러나 조건이 있다. 그것은 바로바로바로..!!!!

정렬된 배열에서만 사용이 가능하다!

선형검색은 어느 배열에서나 사용이 가능하지만 이진 탐색 알고리즘은 Sorted Array에서만 사용이 가능하다.

Sorted Array는 배열의 요소가 순서대로 정렬된 것을 의미한다. 예를 들면 오름차순과 내림차순이 있겠다.

그러나 정렬된 배열을 만들기란 그리 쉽지 않다.
정렬된 배열에 데이터하나를 추가하기 위해서는 각 요소를 하나하나 비교해야하고 저장될위치를 찾으면 그 뒤의 요소들을 뒤로 하나씩 밀어야 하는 단점이 있다.

그러나 고생끝에 낙이 온다!! 이렇게 어렵게 정렬된 배열을 만들어두면 검색시간을 단축해준다는 장점이 있다.(뿌듯뿌듯🥹🥹🥹🥹)

이진 탐색 알고리즘의 '이진(Binary)'이란 하나를 두개로 쪼개는 것을 의미한다.

이진 탐색의 방법은 정렬의 정 중앙에서 시작하여 검색할 데이터의 범위를 반으로 줄여나간다.

1~10까지의 숫자가 있다고 가정했을 때 8이라는 숫자를 찾기 위해선 5를 기준으로 크다,작다를 확인하면 1~4까지의 데이터는 검색할 필요가 없게된다. (선형검색과 비교하자면 무려 9번의 시도가 필요하다)

마찬가지로 1~20의 숫자 중 13이라는 숫자를 찾는다고 가정해보자. 그러나 13이라는 숫자를 찾는 것도 위와 같은 방법으로 한다면 검색횟수에는 큰 차이가 없다.

정리하자면 이렇다.

데이터가 많아졌다고 해서 검색횟수도 많아지지 않는다! 즉, 아무리 데이터가 많아져봤자 이진탐색 알고리즘을 사용한다면 문제없다. (단! 정렬된 배열일 때만 사용가능하다는것 잊지말자!!)

이진탐색은 매 검색마다 절반을 줄여나가기 때문에 효율적인 데이터 처리를 가능하게 한다.

이것이 이진 트리 알고리즘이 필요한 이유다.