[JAVA] 이진탐색(Binary Search)

이진탐색

정렬된 리스트에서 원소를 반으로 분할(분류)하여 특정 값을 찾는 알고리즘

 

1. 중간 값(mid)이 찾고자 하는 값(value)보다 작을 경우 

 => 시작 값(start)이 중간 기준이 되고 다시 중간 값을 도출

 

2. 중간 값(mid)이 찾고자 하는 값(value)보다 클 경우

 => 끝 값(end)이 중간 기준이 되고 중간 값을 다시 도출

 

3. 시작 값이 끝 값보다 클경우 반복문 종료 (start>end)

 

소스코드(반복문)

package 개념;

public class BinarySearch1 {
// 이진탐색 - 반복문
	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6 };
		// ex) 3을 찾을때
		int value = 3;
		int result = BinarySearch(arr, value);
		System.out.println(result);

	}

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

}

 

소스코드(재귀)

package 개념;

public class BinarySearch2 {
	// 이진탐색 - 재귀
	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6 };
		int value = 3;
		int result = BinarySearch(arr, 0, arr.length-1, value);
		System.out.println(result);
	}

	private static int BinarySearch(int[] arr, int start, int end, int value) {
		if(start>end) {
			return end+1;
		}
		
		int mid = (start+end)/2;
		if(value > arr[mid]) return BinarySearch(arr, mid+1, end, value);
		else return BinarySearch(arr, start, mid-1, value);
		
	}

}