[알고리즘] 이진탐색 (이분탐색)

오늘은 이진오늘은 이진탐색 (이분탐색) 에 대해 공부했던 내용을 정리해보려고 한다.

 

이진탐색이란?

이진탐색 (이분탐색) 은 특정 데이터를 탐색하는데 있어 효율적인 방법 중 하나인 알고리즘이다.

이진탐색을 수행하기 위해서는 데이터들이 정렬되어 있어야 한다.

 

이진탐색은 다음과 같은 순서대로 진행한다.

1. 데이터 중 가운데 인덱스와, left 인덱스 (초기 값: 0) 과 right 인덱스 (초기 값: 데이터 배열의 크기 - 1) 을 지정한다.

2. 고른 중앙 값 과 찾고자 하는 값을 비교한다.

3-1. 2의 결과가 중앙 값 > 찾고자 하는 값인 경우 : left 인덱스를 mid 인덱스 + 1 만큼으로 수정한다.

3-2. 2의 결과가 중앙 값 < 찾고자 하는 값인 경우 : right 인덱스를 mid 인덱스 - 1 만큼으로 수정한다.

4. 이후 left 인덱스 값이 right 인덱스 값보다 큰 경우가 되기 전까지 반복하여 찾으면 반복을 중단한다.

 

왜 이진탐색을 사용할까?

기존 배열에서 원하는 값을 찾으려면 처음부터 끝까지 반복하면서 찾는 방법을 사용해야한다.

따라서 성능이 좋지 않을 수 밖에 없다. 그러나 이진탐색을 사용한다면, 탐색을 반복할때마다

범위가 줄게 되므로 성능이 개선됨을 알 수 있다.

 

이진탐색의 최대 반복횟수는 log 2 의 n 만큼이므로 굉장히 효율적이다.

 

Java 로 구현해보기

int left = 0;
int right = arr.length - 1;
int mid = 0;
boolean result = false;

while (left <= right) {
	mid = (left + right) / 2;
    if(arr[mid] < i){
    	left = mid + 1;
    }
    else if(arr[mid] > i){
        right = mid - 1;
    }
    else{
        result = true;
        break;
    }
}