알고리즘 - 이분 탐색 (Binary Search)

안녕하세요, 알고리즘을 정리하는 포스팅입니다. 다른 알고리즘을 참고하시려면 해당 카테고리를 이용해주세요. 😊

'🌻 JAVA/알고리즘, 자료구조' 카테고리의 글 목록

 

이분 탐색 (Binary Search)

이분 탐색은 탐색 범위를 두개로 나눠서 탐색하기 때문에 훨씬 빠른 탐색 알고리즘입니다.

 

처음부터 차례대로 탐색 : O(N)
시간 복잡도 : O(log N)

 

 

과정

0. 탐색하기 위한 배열, 찾고자 하는 값 : 9 (이하 Target)

 

1. 먼저 배열을 정렬시킵니다.

 

2. 인덱스 L, R, MID를 지정해줍니다.

 

3.  if (Target == arr[M])

if(target == arr[M]) {
	return M;
}

 

4. else if (Target > arr[M])

M 이하의 수들은 범위에서 제외합니다.

 

5. else if (Target < arr[M])

M 이상의 수들은 범위에서 제외합니다.

 

6. 다시 2번 과정으로 돌아갑니다.

 

전체 코드 (Code)

public int binary_Search(int[] arr, int target) {

    // 정렬이 안되어있다면, 정렬 먼저!
    Arrays.sort(arr);
    
    int L = 0, R = arr.length-1, M = 0;
    
    while(L != R) {
    	M = (L + R) / 2;
        
        if(target == arr[M])	return M;
        else if(target > arr[M]) {
        	L = M + 1;
        } else {	// target < arr[M]
        	R = M - 1;
        }
    }
    return -1;
}