이분탐색(Binary Search)

이분탐색(Binary Search)

순차탐색보다 빠른 탐색을 위한 탐색 기법으로, 정렬된 배열 또는 리스트에 적합한 고속 탐색 기법이다.

---

정렬된 배열에서 순차탐색과 이분탐색의 차이

순차탐색

• 특정 원소를 찾기 위해 0번 인덱스부터 차례대로 탐색한다.
• 원소를 건너뛰지 않고 순차적으로 탐색한다.
• 시간복잡도 - O(n)

이분탐색

• 특정 원소를 찾기 위해 i번 인덱스부터 j번 인덱스의 중간값과 비교한다.
• 중간값이 찾는 원소가 아니라면 i - j 범위를 다시 정한다.
• 탐색할 때마다 범위가 반으로 줄어든다.
• 시간복잡도 - O(logn)

이분탐색 과정

1. 처음 범위는 0번 인덱스부터 끝까지이며, 중간 인덱스를 mid로 설정한다.
   mid = (left + right) / 2
2. mid(중간 인덱스의 값)와 find(찾는 원소의 값)를 비교한다.
   1) mid == find : 탐색 종료
   2) mid < find : left = mid + 1, 2번 반복
   3) mid > find : right = mid -1, 2번 반복
3. right > left인 경우 해당 배열에 찾는 원소가 없는 것이다.

이분탐색 구현방법

• 반복문 구현

	private boolean binarySearch(int[] arr, int find) {
		int left = 0;
		int right = arr.length - 1;
		int mid;

		while (left <= right) {
			mid = (left + right) / 2;
			if (arr[mid] < find) left = mid + 1;
			else if (arr[mid] > find) right = mid - 1;
			else return true;
		}
        
		return false;
	}

• 재귀함수 구현

	private boolean binarySearch(int[] arr, int find, int left, int right) {
		if(left > right) return false;
		
		int mid = (left + right) / 2;
        
		if (arr[mid] < find) 
        	return binarySearch(arr, find, mid + 1, right);
		else if (arr[mid] > find) 
        	return binarySearch(arr, find, left, mid - 1);
		else 
        	return true;
	}