알고리즘 이진탐색(Binary Search) 그림으로 쉽게 이해하기

알고리즘 이진탐색(Binary Search) 그림으로 쉽게 이해하기

 

안녕하세요.

 

로스윗의 코딩캠프입니다.

 

오늘은 정렬 알고리즘 중에서

 

이진탐색(Binary Search)에 대한 포스팅을 진행하겠습니다.

 

정말 어렵지 않으니 잘 따라와주세요!!

 

 

 

 

 

우선 저희가 이번 포스팅에서 배울 이진탐색(Binary search)은 

 

이후에 배울 정렬과는 조금 다른 내용이기는 합니다.

하지만 정렬을 공부하기 전에 먼저 이진탐색(binary search)에 대해서 이해하고 있어야

 

이후의 내용을 공부할 때 좀 더 수월하기 때문에

 

이진탐색(Binary search)에 대해서 먼저 다뤄보도록 하겠습니다.

 

 

 

 

-이진 탐색(Binary Search)이란?

이진탐색(Binary search)이란

 

-> 오름차순 정렬되어 있는 리스트 내에서 특정값의 인덱스를 찾는 알고리즘 입니다.

 

예시를 한 번 보겠습니다.

 

 

이진 탐색 예시

1부터 20까지의 숫자리스트에서 

 

숫자 7의 위치가 몇 번째의 인덱스 위치에 들어있는지 찾기 위한 가장 효율적인 방법은 무엇일까요?

숫자가 정렬되어 있는 것은 보장이 되어 있지만

 

이때 이 안에 있는 숫자들이 모두 연속된 숫자임을 의미하지는 않습니다.

보시면 아시겠지만 중간에 건너뛴 숫자들이 존재해요. 

 

그렇기 때문에 숫자 7의 값을 찾기 위해서 꼭 7번째 인덱스 위치에 숫자가 있지 않을 수 있습니다.

그래서 이 상황에서 우리는 가장 효율적으로 숫자를 찾는 방법을 생각해야 합니다.

 

물론 리스트의 처음부터 끝까지 쭉 값을 하나씩 비교해보면서 값을 찾는 방법도 있지만 

 

이 방법은 데이터의 크기가 커질수록 비효율적이겠죠.

- 그렇다면 효율적인 방법은 무엇일까요?

우선 리스트에서 가장 중간에 위치한 인덱스의 값을 먼저 찾아갑니다.

그렇다면 가장 중간에 위치한 값은 11인걸 알수 있죠. 

 

 

가장 중간 값은 11

 

그리고 이 배열은 정렬이 되어 있다는 조건이 붙어있기 때문에

11보다 작은 값은 무조건 11보다 왼쪽에 있을 것이고, 11보다 큰 값은 무조건 오른쪽에 있을 것입니다. 

그러면 우리가 찾아야 하는 값 7은 11보다 작기 때문에 11의 왼쪽 리스트만 찾으면 그 중 어딘가에 7이 있을거에요.

이때 11역시도 우리가 찾는 값이 아니기 때문에

 

굳이 11까지 포함해서 보지 않아도 11이 위치한 바로 앞에 인덱스 위치까지만 보면 되겠죠.

그럼 여기서도 앞에서 한 동작을 동일하게 적용해볼게요.

우리가 데이터를 절반으로 줄여서 얻은 이 리스트에서 중간 인덱스에 위치한 값은 5입니다.

 

 

그 다음 중간 값은 5

마찬가지로 5의 왼쪽에는 5보다 작은 값들이 있을거구요, 5의 오른쪽에는 5보다 큰 값이 있을거에요.

 

우리가 찾고자 하는 값 7은 5는 5보다 크기 때문에 5의 오른쪽에 있겠죠.

 

그래서 여기서도 5를 포함하지 않고 7~10까지의 새로운 서브 리스트를 찾아낼 수 있습니다.

 

여기서도 동일 동일하게 중간값 9를 가져옵니다

 

그 다음 중간값은 9

 

우리가 찾고자하는 값 7이 9보다 큰지 작은지를 비교해서 값의 위치를 찾아나갈 수 있습니다.

이것이 Bicary search즉 이진탐색입니다. 

Binary 뜻 자체가 숫자 둘을 의미합니다.

 

 한 번의 수행마다 절반씩 둘로 나뉘어 가면서 사이즈를 줄여나가기 때문에 

 

Binary search라고 이름이 붙게 되었습니다.

 

 

- 이진탐색(Bicary Search)의 특징

그래서 이진탐색(Binary search)는 한 번의 시행마다 우리가 봐야할 데이터의 크기가

 

절반씩 훅훅 줄어든다는 특징이 있어요.

그래서 밑이 2인 logN번만 분할하면 데이터 리스트의 값을 찾아오는게 가능하기 때문에 

 

logN의 시간 복잡도를 갖게 됩니다.

시간 복잡도 O(N)과 비교했을 때 어느정도의 차이가 있냐면 

 

총 데이터가 100개인 리스트가 주어졌다고 가정 했을 때

앞에서부터 하나씩 값을 비교하면서 데이터를 찾게 된다면 최대 100번의 연산 수행을 해야하는 반면 

이진탐색(Binary search)로 값을 찾게 된다면 어떤 경우라도 6.64번, log100의 값이죠. 

 

이것을 자연수로하면 최대 7번 내에는 값을 찾을 수 있다는 의미가 됩니다.

데이터의 크기가 더 커질수록 이 수행의 크기 차이는 더 커지겠죠.

그렇다면 우리가 그동안 구현했던 자료구조에서 index of라는 method를 구현했던 것을 기억하시나요?

이걸로 원소의 위치를 찾기 위해 이진탐색(Binary search)를 적용하면

 

더 빨리 값을 찾을 수 있는게 아닌가 하는 생각을 해볼 수 있어요.

하지만 이진탐색(binary search)는 정렬된 리스트에서만 사용이 가능하다는 제약이 존재하기 때문에

 

데이터의 값이 정렬되어 있다는 보장이 되어 있지 않다면 쓸 수 없는 방법이라는 조건이 함께 따라옵니다.

 

로스윗의 코딩캠프는

 

미래의 개발자 여러분을 응원합니다.

 

모두 화이팅!!

 

자료구조 - 해시(Hash)란? (ft. 가장 쉬운 비유 설명)

자료구조 해시(Hash)란? (ft. 가장 쉬운 비유 설명)

자료구조 스택(stack)이란? (ft. 그림으로 쉽게 설명)

자료구조 스택(stack)이란? (ft. 그림으로 쉽게 설명)