[알고리즘] 이분(이진)탐색

이분 탐색

배열 등 자료를 두 부분으로 쪼개어 탐색하는 방법
특정 값 또는 자료가 존재하는지를 탐색할 때 사용함
이분 탐색을 위한 배열은 정렬되어 있어야 함

 

- 로직
1) 탐색 배열의 내 중간 인덱스( (시작 인덱스 + 끝 인덱스) / 2 )를 구함
2) 배열[중간 인덱스]에 위치한 값과 찾으려는 값 비교
3) 비교 결과를 통해 반복 여부 결정
  3-1) 배열 값과 같으면 중간 인덱스 반환
  3-2) 배열 값이 작으면 "중간 인덱스 + 1"를 시작 인덱스로 지정
  3-3) 배열 값이 크면 "중간 인덱스 - 1"를 끝 인덱스로 지정
4) 인덱스 범위가 하나가 될 때까지 1) 2) 3)을 반복
    -> 만약 인덱스 범위가 1인데 값이 다르다면 해당 값은 존재하지 않는 값

 

 

코드

public class 이분탐색_기본 {
	public static void main(String[] args) throws Exception {
		int[] arr = {9, 1, 3, 5, 7, 8};

		Arrays.sort(arr); // 정렬

		int search = 8;

		int answer = 0; // 베열 내 있으면 1 없으면 0 반환
		int start = 0; // 배열의 시작 위치
		int end = arr.length - 1; // 배열의 끝 위치
		

		System.out.print("탐색 순서 : ");
		while (start <= end) {
			int mid = (start + end) / 2; // 배열의 중간 위치
			System.out.print(mid + " ");

			// 찾으려는 값보다 배열에 들어가 있는 값이 더 작다면
			if (search > arr[mid]) {
				start = mid + 1; // 현재 중간 값보다 오른쪽에 있다는 뜻
			}

			// 찾으려는 값보다 배열에 들어가 있는 값이 더 크다면
			if (search < arr[mid]) {
				end = mid - 1; // 현재 중간 값보다 왼쪽에 있다는 뜻
			}

			// 찾으려는 값과 배열에 들어간 값이 같다면
			if (search == arr[mid]) {
				end = arr[mid];
				answer = 1;
				break;
			}

		}
		System.out.println();
		System.out.println(answer); // 1

	}
}

 

 

 

추천 문제

백준 1920 수 찾기 (기본 문제)

https://angelplayer.tistory.com/432