📖 이분 탐색

---

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
• 이분 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
• 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
• 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정
• 시간 복잡도 : O(log N)

💬 탐색 과정

---

1. 자료의 중앙 원소 고름

2. 중앙 원소 값과 찾고자하는 목표 값 비교

3. 목표 값이 중앙 값보다 작으면 왼쪽 구간 탐색 수행, 크면 오른쪽 구간 탐색 수행

4. 원하는 답을 찾을 때까지 반복

💬 알고리즘 구현

• 자료의 시작점과 종료점을 이용해서 검색

---

public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
		binarySearch(arr, 2); // 2의 인덱스 찾기
	}

	static int binarySearch(int[] arr, int target) {
		int start = 0, end = arr.length-1;
		int mid;
		
		int result = 0;
		while(start <= end) {
			mid = (start + end) / 2;
			
			if(arr[mid] < target) start = mid+1;
			else if(arr[mid] > target) end = mid-1;
			else {
				result = mid;
                break;
			}
		}
		return result;
	}