[탐색] 이진탐색(이분탐색)

📌 이진탐색(Binary Search)

⭐ 개념

• 데이터가 정렬되있어야 한다
• 대상 데이터의 중간값과 찾고자 하는값을 비교해 절반씩 줄이면서 대상을 찾는 알고리즘
• 탐색 범위를 두 부분으로 분할하면서 찾는 방식

✅ 시간복잡도 : O(log N)

⭐ 탐색과정

1. 데이터셋의 중앙값(median)을 선택
2. 중앙값 > 타깃값 이면, 중앙값기준 왼쪽 데이터셋을 선택
3. 중앙값 < 타깃값 이면, 중앙값기준 오른쪽 데이터셋을 선택
4. 1~3을 반복하면서 중앙값 == 타깃값일때 탐색종료

⭐ 코드

public class Main {
	static int[] arr = {1, 3, 5, 7, 8, 13, 22, 57, 91, 100};

	public static void main(String[] args) {
    	// 13을 찾아보자.
		binarySearch1(13, arr[0], arr[arr.length()-1]);	
        binarySearch2(13, arr[0], arr[arr.length()-1]);	
	}
	
	// 재귀적 탐색
	static int binarySearch1(int key, int low, int high) {
		int mid;
		if(low <= high) {
			mid = (low + high) / 2;
			if(key == arr[mid]) { // 탐색 성공 
				return mid;
			} else if(key < arr[mid]) {
				return binarySearch1(key ,low, mid-1); // 왼쪽 부분 탐색 
			} else {
				return binarySearch1(key, mid+1, high); // 오른쪽 부분 탐색 
			}
		}
		
		return -1; // 탐색 실패 
	}
	
	// 반복적 탐색
	static int binarySearch2(int key, int low, int high) {
		int mid;
		while(low <= high) {
			mid = (low + high) / 2;
			if(key == arr[mid]) {
				return mid;
			} else if(key < arr[mid]) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		return -1; // 탐색 실패 
	}

}