[배열 검색] 이진 검색

 

 

이진 검색은 선형 검색보다 빠르게 검색할 수 있는 검색 알고리즘이다. 

 

이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서만 사용할 수 있는 알고리즘이다.

 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("요솟수를 입력하세요: ");
		int N = sc.nextInt();
		int[] arr = new int[N];

		System.out.println("오름차순으로 입력하세요.");

		System.out.print("arr[0]: ");
		arr[0] = sc.nextInt();
		for (int i = 1; i < arr.length; i++) {
			do {
				System.out.print("arr[" + i + "]: ");
				arr[i] = sc.nextInt();
			} while (arr[i] < arr[i - 1]); // 바로 앞의 요소보다 작으면 다시 입력.
		}

		System.out.print("검색할 값: ");
		int key = sc.nextInt();

		int idx = binSearch(arr, key, N);
		if (idx == -1) {
			System.out.println("그 값의 요소는 없습니다.");
		} else {
			System.out.printf("%d은(는) arr[%d]에 있습니다.", key, idx);
		}
	}

	static int binSearch(int[] arr, int key, int n) {
		int pl = 0;
		int pr = n - 1;

		do {
			int pc=(pl+pr)/2; //배열의 중앙값
			if(arr[pc]<key) {  //key 값이 더 크면
				pl=pc+1;
			}else if(key<arr[pc]) {//key 값이 더 작으면 
				pr=pc-1;
			}else {
				return pc;
			}
		} while (pl <= pr);

		return -1;
	}
}

오름차순 이진검색

 

 

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("요솟수를 입력하세요: ");
		int N = sc.nextInt();
		int[] arr = new int[N];

		System.out.println("내림차순으로 입력하세요.");

		System.out.print("arr[0]: ");
		arr[0] = sc.nextInt();
		for (int i = 1; i < arr.length; i++) {
			do {
				System.out.print("arr["+i+"]: ");
				arr[i]=sc.nextInt();
			}while(arr[i]>arr[i-1]);
		}

		System.out.print("검색할 값: ");
		int key = sc.nextInt();

		int idx = binSearch(arr, key, N);
		if (idx == -1) {
			System.out.println("그 값의 요소는 없습니다.");
		} else {
			System.out.printf("%d은(는) arr[%d]에 있습니다.", key, idx);
		}
	}

	static int binSearch(int[] arr, int key, int n) {
		int pl = 0;
		int pr = n - 1;

		do {
			int pc=(pl+pr)/2;
			if(arr[pc]==key) {
				return pc;
			}else if(arr[pc]<key) {
				pr=pc-1;  //pr을 index 감소시킴
			}else {
				pl=pc+1;  //pl을 index 증가시킴
			}
		} while (pl <= pr);

		return -1;
	}
}

내림차순 이진 검색

 

요솟수를 입력하세요: 5
내림차순으로 입력하세요.
arr[0]: 50
arr[1]: 45
arr[2]: 22
arr[3]: 10
arr[4]: 1
검색할 값: 22
22은(는) arr[2]에 있습니다.

 

 

 

 

복잡도

알고리즘 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다.

복잡도는 2가지 요소를 가지고 있다.

1. 시간 복잡도(time complexity): 실행에 필요한 시간을 평가하는 것.

2. 공간 복잡도(space complexity): 기억 영역과 파일 공간이 얼마나 필요한가를 평가하는 것.

 

 

이진 검색의 시간 복잡도는 

static int binSearch(int[] arr, int key, int n) {
		int pl = 0;  //1
		int pr = n - 1;  //2

		do {
			int pc=(pl+pr)/2;  //3
			if(arr[pc]==key) {  //4
				return pc;  //5
			}else if(arr[pc]<key) {  //6
				pr=pc-1;    //7
			}else {
				pl=pc+1;   //8
			}
		} while (pl <= pr); //9

		return -1;  //10
}

주석에 숫자들이 단계이다.

 

단계	실행횟수	복잡도
1	1	O(1)
2	1	O(1)
3	log n	O(log n)
4	log n	O(log n)
5	1	O(1)
6	log n	O(log n)
7	log n	O(log n)
8	log n	O(log n)
9	log n	O(log n)
10	1	O(1)

(복잡도를 표기할 때 사용하는 O는 Order를 뜻한다. O(n)은 'O-n', 'Order n', 'n의 Order'라고 읽는다.)

 

복잡도는 차원이 가장 높은 복잡도를 선택한다.

그래서,

O(1)+O(1)+O(log n)+O(log n)+....+O(1)= O(log n)

따라서, 위 이진 검색 메서드의 시간 복잡도는 O(log n)이다.

 

 

 

복잡도와 증가율

 

 

 

---

 

Arrays.binarySearch 메서드

 

 

java.util 패키지에 있는 Arrays 클래스 내에 binarySearch 메서드는 위에 코드들처럼 손 수 이진 검색 알고리즘을 작성하지 않고 사용할 수 있는 메서드이다.

 

 

binarySearch는 요소수를 찾을 시 해당 index를 반환한다.

만약 못 찾을 경우에는 

반환 값은 삽입 포인트 x라고 할 때 -x-1을 반환한다.

삽입 포인트는 지정한 key보다 큰 요소 중 첫 번째 요소의 인덱스가 삽입 포인트이다.

 

 

만약, arr {5.10.15,20} 배열에서 11을 검색하면 

11보다 큰 요소는 15이다. 15의 값을 가진 요소의 index는 2이므로

-2-1 = -3

-3을 반환하게 된다.

 

 

 

 

위 그림처럼 key값이 요소들보다 전부 다 클 경우 마지막 인덱스 바로 뒤에 임시로 길이를 1 추가해  -추가된 index-1을 반환한다.

 

 

import java.util.*;  //Arrays.binarySearch 사용하기 위한 import

public class Search {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		System.out.print("요소수를 입력하세요: ");
		int N = sc.nextInt();
		int[] arr = new int[N];
		System.out.print("arr[0]: ");
		arr[0] = sc.nextInt();

		for (int i = 1; i < arr.length; i++) {
			do {
				System.out.print("arr[" + i + "]: ");
				arr[i] = sc.nextInt();
			} while (arr[i] < arr[i - 1]);
		}
		System.out.print("찾으려는 요소값은?: ");
		int key = sc.nextInt();
		int value = Arrays.binarySearch(arr, key);
		if (value < 0) {
			System.out.println("찾으려는 요소값은 없습니다." + value);
		} else {
			System.out.println("찾으려는 " + key + "는 arr[" + value + "]에 있습니다.");
		}
	}

}

 

요소수를 입력하세요: 5
arr[0]: 1
arr[1]: 2
arr[2]: 3
arr[3]: 4
arr[4]: 5
찾으려는 요소값은?: 4
찾으려는 4는 arr[3]에 있습니다.

binarySearch메서드로 검색을 성공한 경우

 

요소수를 입력하세요: 4
arr[0]: 15
arr[1]: 52
arr[2]: 88
arr[3]: 100
찾으려는 요소값은?: 87
찾으려는 요소값은 없습니다.-3

찾으려는 요소 값이 존재하지 않는다면.

 

 

 

 

 

Arrays.binarySearch에 의한 이진 검색의 장점은 

1. 이진 검색 메서드를 직접 코딩하지 않아도 된다.

2. 모든 자료형 배열에서 검색할 수 있다.

 

import java.util.*;

public class langTest {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] strArr = { "Java", "C", "C++", "Python" };

		String key = sc.next();

		int idx = Arrays.binarySearch(strArr, key);

		if (idx < 0) {
			System.out.println("해당 문자열은 존재하지 않습니다.");
		} else {
			System.out.println("해당 문자열은 strArr[" + idx + "] 에 있습니다.");
		}
	}
}

C++
해당 문자열은 strArr[2] 에 있습니다.

검색 성공

python
해당 문자열은 존재하지 않습니다.

p가 소문자라 검색 실패

 

 

 

위에 코드처럼 binarySearch메서드는  모든 자료형 배열에서 검색할 수 있다는 장점이 있다.

 

 

 

 

참고하면 좋은 자료

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

 

 

 

 

 

 

커버 사진

https://www.flaticon.com/kr/premium-icon/algorithms_3988792?term=%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98&page=1&position=7&page=1&position=7&related_id=3988792&origin=search 

<a href="https://www.flaticon.com/kr/free-icons/" title="연산 아이콘"> 연산 아이콘  제작자: khld939 - Flaticon </a>