이진탐색 binarySearch with swift

전화번호부에서 이름을 검색할 때 이진 탐색을 사용한다. 

 

이전 프로젝트에서도 전화번호부에서 이름을 검색해야 했는데 배열의 처음부터 다 매칭 해보는 방법을 사용해 O(n)의 시간 복잡도를 가졌습니다. 그때 이진 탐색을 사용했더라면 O(logn)의 시간 복잡도를 가져 배열이 길수록 훨씬 더 효율적으로 검색할 수 있었겠죠. ㅠ_ㅠ

사실 이진 탐색 알고리즘이 무엇인지는 학교에서 배워서 대충은 알고 있었으나 실전에서 이렇게 사용되는지는 와 닿지 않았습니다.

 

그래서 이번 기회에 이진 탐색 알고리즘을 학습하고 정리하려 합니다.

먼저 이진 탐색 알고리즘의 조건은 데이터가 정렬되어 있어야 합니다.

스위프트로 작성한 코드를 봅시다.

중간 인덱스를 찾아서 중간 인덱스의 값이랑 비교를 합니다.

 

중간 인덱스 값과 내가 원하는 값이 같다면 원하는 값의 위치를 찾은 거니 return을 해줍니다.

여기서 middle이 내가 찾고자한 값의 위치(index)가 되겠네요.

 

중간 인덱스 값 보다 내가 원하는 값이 더 작다면 원하는 값이 더 작다는 의미니 다시 binarySearch를 호출합니다. 

이때 파라미터 end에는 middle -1을 해준 값으로 호출합니다.

왜냐하면 정렬되어 있기 때문에 middle보다 아래에(왼쪽에) 있다고 확신할 수 있기 때문입니다.

 

중간 인덱스 값 보다 내가 원하는 값이 더 크다면 원하는 값이 더 크다는 의미니 다시 binarySearch를 호출합니다.

이때 파라미터 start에는 middle + 1을 해준 값으로 호출합니다.

왜냐하면 정렬되어 있기 때문에 middle보다 위에(오른쪽에) 있다고 확신할 수 있기 때문입니다.

 

 

예를 들어

위와 같이 정렬된 배열이 있다고 가정합니다.

binarySearch함수에 배열과 start, end 인덱스와 찾고자 하는 값 answer을 넣어줍니다.

시작 인덱스는 0 끝 인덱스는 5겠네요. 그리고 4를 찾는다고 가정해봅니다.

binarySearch(array: array, start: 0, end: 5, answer: 4)

이렇게 호출되겠네요.

우리가 찾을 범위입니다. 인덱스 0부터 5까지 middle값은 2가 됩니다.

if문을 봅시다.

array[2] == 4가 같은지 확인합니다.

array [2]는 3이므로 4와 다릅니다.

그러므로 아래 else if 문으로 내려옵니다.

 

else if문에서 array [2]즉 3 > 4 가 true가 아니기 때문에 조건문은 성립되지 않고 아래로 내려옵니다.

 

else 문을 실행합니다.

재귀 함수로 binarySearch함수를 또 호출합니다.

binarySearch(array: array, start: 3, end: 5, answer: 4)

이렇게 호출되겠네요.

 

우리가 찾을 범위 입니다. 인덱스는 3에서 5까지 middle은 4가 됩니다.

if문을 봅시다.

array[4] == 4가 같은지 확인합니다.

array [4]는 5이므로 4와 다릅니다.

그러므로 아래 else if 문으로 내려옵니다.

 

else if문에서 array [4]즉 5 > 4 가 true기 때문에 조건문이 성립되어 else if 문이 실행됩니다.

재귀 함수로 binarySearch함수를 또 호출합니다.

binarySearch(array: array, start: 3, end: 3, answer: answer)

이번엔 이렇게 호출되겠네요.

우리가 찾을 범위 입니다. 인덱스는 3에서 3까지 middle은 3이 됩니다.

if문을 봅시다.

array[3] == 4가 같은지 확인합니다.

array [3]은 4이므로 4와 같습니다.

그럼 print문으로 4 찾았다가 출력되고 return 되어 종료가 됩니다.

이렇게 우리가 찾을려는 4는 배열의 인덱스 3에 위치한다는 정보를 얻을 수 있게 됩니다. 

 

계속해서 검색하는 범위가 줄어드는 게 보이시나요.

배열의 길이가 길어도 logn의 시간 복잡도를 가지니 효율적으로 검색할 수 있는 방법이라고 할 수 있습니다.