이진 탐색 - 알고리즘

👩‍💻  이진 탐색 (Binary Search) 란?

이진 탐색은 (= 이분 탐색) 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법이다.

• 찾고자 하는 값과 데이터 중앙에 있는 값을 비교
• 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색
• 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색

 

✏️ 시간 복잡도

알고리즘 시간 복잡도 : O(logN)

 

✏️ 이진 탐색 과정

* 데이터가 우선 정렬된 상태여야 이진 탐색 진행이 가능하다.

찾고자 하는 데이터 x를 기준으로 mid 값과 비교하여 범위를 줄여나가며 찾아가는 방식이다.

 

✏️ 이진 탐색 구현 과정

✨ 반복문 구조

public class Main{
	public static int binarySearch(int arr[], int target){
    	int left = 0;
        int right = arr.length - 1;
        
        while(left <= right){
        	int mid = (left + right) / 2;
            
            if(target == arr[mid]){
            	return mid;
            }else if(target < arr[mid]{
            	right = mid - 1;
            }else{
            	left = mid + 1;
            }
        }
        
        return -1;
    }
}

 

 

✨ 재귀 호출 구조

public class Main{

	public static int binarySearch2(int[] arr, int target, int left, int right){
    	if(left > right){
        	return -1;
        }
        int mid = (left + right) / 2;
        
        if(target == arr[mid]){
        	return mid;
        }else if(target < arr[mid]){
        	return binarySearch2(arr, target, left, mid-1);
        }else{
        	return binarySearch2(arr, target, mid+1, right);
        }
    }

}

 

 

✏️ Java에서 기본 제공 되는 Binary Search

Arrays.binarySearch(arr, 1); // 배열 arr에서 1을 찾는 경우
Arrays.binarySearch(arr, 10); // 배열 arr에서 10을 찾는 경우

 

만약, 배열에서 binarySearch를 사용했을때 찾고자 하는 값이 없다면 

찾고자 하는 값이 있었다면 있어야 할 위치의 index * (-1) 값이 반환된다.

즉, 그 값이 있었어야 할 자리의 인덱스 값에 마이너스가 붙은 값이 반환된다.

 

(ex)

if arr = {1,2,3,5,6,7}, search value = 4

then, Arrays.binarySearch(arr,4) running -3 (4가 존재했다면 index 3번 위치에 있었어야 하므로)