[Algorithm] 배열에서 이진검색 - JAVA

이진 검색 : 규칙이 있는 데이터 배열에서 아주 빠른 검색 수행

오름차순 혹은 내림차준으로 정렬된 배열에서 8 찾기.

1. 중앙에 위치한 요소인 array[4] 부터 검색을 시작
2. 검색하려는 값 8이 중앙값보다 크기 때문에, 중앙값 기준 뒤의 숫자 중 중앙값인 7과 비교
3. 검색하려는 값 8이 7보다 크기 때문에, 7 기준 뒤의 숫자와 비교한 후 8 찾기

package exercise;
import java.util.Scanner;

public class test2 {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int num = stdIn.nextInt();
		int[] array = new int[num];
		
		array[0] = stdIn.nextInt();
		
		for (int i = 1; i < num; i++) {
			do {
				array[i] = stdIn.nextInt();
			} while (array[i] < array[i-1]);
		}
		
		int search_num = stdIn.nextInt();
		
		int searched_index = search_array(num, array, search_num);
		
		if (searched_index == -1) {
			System.out.println("value does not exist");
		}
		else {
			System.out.println(search_num + " exists in index " + searched_index);
		}
	}

	static int search_array(int size, int[] array, int search_num) {
		int left_index = 0;
		int right_index = size - 1;
		
		do {
			int mid_index = (left_index + right_index) / 2;
			
			if (array[mid_index] == search_num)
				return mid_index;
			else if (array[mid_index] < search_num)
				left_index = mid_index + 1;
			else
				right_index = mid_index - 1;
		} while (left_index <= right_index);
		
		return -1;
	}
}