이분 탐색(Binary Search)

1. 이분 탐색(Binary Search)

: 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법이다.

📌 특징

• 탐색의 범위를 반으로 줄인다 ⇒ 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지 찾는 방법
  
• 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있다. ⇒ 찾고자 하는 값이 속해있지 않은 부분은 고려할 필요가 없다.
  
• 데이터의 삽입이나 삭제가 자주 발생하는 경우에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합하다.

---

2. 이분 탐색 방법

1. 처음 시작하는 범위는 인덱스 0부터 배열의 마지막 인덱스까지이다. 이때 중간 인덱스를 mid로 한다.
low = 0;
high = array.length()-1;
mid = (low+high)/2;

2. mid의 값과 찾는 원소를 비교한다.
	2-1) 내가 찾는 원소가 array[mid]에 존재한다면 탐색을 종료한다.
	2-2) array[mid] < 내가 찾는 원소
				→ 이때는 low = mid + 1; 로 바꿔주고 계속 탐색을 진행한다.
	2-3) array[mid] > 내가 찾는 원소
				→ 이때는 high = mid - 1; 로 바꿔주고 계속 탐색을 진행한다.

3. 만약 high < low가 된다면 해당 배열에 찾는 원소가 없는 것이다. 

---

3. 이분 탐색 구현

import java.util.Arrays;

public class 이분탐색구현_반복문 {
	
	static int[] array = {3,6,2,1,9,5};
	
	static int findNumber;
	
	public static void main(String[] args) {
		
		// 오름차순으로 정렬
		Arrays.sort(array);
		
		System.out.println(Arrays.toString(array));
		
		findNumber = 5;
		
		
		int low = 0;
		int high = array.length-1;
		int mid;
		
		while(low<=high) {
			mid = (low+high)/2;
			if(array[mid] == findNumber) {
				System.out.println(mid+"번 인덱스에 "+array[mid]+"가 존재합니다.");
				break;
			}else if(array[mid] < findNumber) {
				low = mid + 1;
			}else {
				high = mid - 1;
			}
		}
	}
}

import java.util.Arrays;

public class 이분탐색_재귀 {
	
	static int[] array = {3,6,2,1,9,5};
	
	static int findNumber;
	
	public static void main(String[] args) {
		
		// 오름차순으로 정렬
		Arrays.sort(array);
		
		System.out.println(Arrays.toString(array));
		
		findNumber = 5;
		
		binarySearch(0, array.length-1);
	}
	
	static void binarySearch(int low, int high) {
		if(low > high)
			return;
		
		int mid = (low+high)/2;
		
		if(array[mid] == findNumber) {
			System.out.println(mid+"번 인덱스에 "+array[mid]+"가 존재합니다.");
			return;
		}else if(array[mid] < findNumber) {
			low = mid+1;
		}else {
			high = mid-1;
		}
		binarySearch(low, high);
		
	}
}

---

4. 시간복잡도

• 순차적 탐색 : 최악의 경우에는 배열에 존재하는 데이터를 모두 탐색하기 때문에 O(n)이다.
• 이분 탐색 : 범위를 새로 정할 때 마다 탐색 범위는 1/2씩 줄어든다. 따라서 시간복잡도는 O(log n)이다.