자바 이진검색(Binary Search) 알고리즘 정리

이진검색(Binary Search) 알고리즘은

정렬되어 있는 데이터를 절반씩 나눠 검색하는 방식인데

순차 검색 방법이 모든 데이터를 다 확인해본다면

이진 검색은 데이터를 절반으로 나눠가면서 찾게 된다

 

먼저 데이터가 오름차순으로 되어있지 않을 때는

오름차순으로 데이터를 정렬하고

low는 0으로 (배열의 처음 인덱스)

high는 해당 배열의 마지막 인덱스로 초기화한다

 

다음은 while을 돌려주면서

low + high / 2 를 해서 mid 값을 구하는데

mid를 배열의 인덱스로 넣었을 경우의 값이

찾는 값과 동일하다면 바로 끝이 나지만

 

그렇지 않을 경우에는

해당 값이 찾는 값(Search)보다 크냐 작냐에 따라

low, high를 바꿔주게 되는데

 

Search 값이 mid를 배열의 인덱스로 넣었을 경우보다 작다면

low = mid + 1

 

크다면

high = mid - 1

 

이런 식으로 값을 변경한 뒤

mid를 다시 설정한 후

맞는 값을 찾을 때까지 값을 찾게 된다

(없을 경우 low와 high가 같아지면서 끝남)

 

이진 검색에서 포인트는

반드시 정렬이 되어 있어야 하고

찾는 값이 현재 mid를 배열 인덱스로 넣을 때보다

크다면 low를 1 올려주고

작다면 high를 1 내려서

 

절반씩 이동하면서 찾는 방식이기 때문에

위 원리를 꼭 이해해두어야 한다

 

마지막으로 예제에 사용한 코드는 다음과 같다

 

	public static void main(String[] args) {
		// 이진검색 알고리즘(Binary Search Algorithm)
		// '정렬되어 있는' 데이터를 이진 검색을 사용하여 반씩 나눠 검색
		int[] arr = {1, 7, 3, 5, 9}; // 데이터는 무조건 정렬되어 있어야 함
		Arrays.sort(arr); // 배열 오름차순 정렬
		
		int search = 9; // 찾을 값
		boolean flag = false; // 값을 찾았을 경우 flag
		int answer = -1;
		int low = 0;
		int high = arr.length - 1;
		
		while(low <= high) {
			int mid = (low + high) / 2; // 중간값은 low + high / 2
			if(arr[mid] == search) { // search와 같을 경우
				flag = true;
				answer = mid;
				break;
			}
			if(arr[mid] < search) { // 값이 search 보다 작다면 low + 1
				low = mid + 1;
			} else { // 값이 search 보다 크다면 high - 1
				high = mid - 1;
			}
		}
		
		if(flag == true) { // 검색 값이 있다면
			System.out.println("배열의 다음 인덱스와 동일 : " + answer);
		} else { // 없다면
			System.out.println("Search 값에 해당하는 값이 없습니다");
		}
	}