이진탐색(binary search)란?
정렬되어 있는 자료들의 집합에서 특정한 자료를 찾으려고 할때 사용되고 매우 빠른 검색 알고리즘이다. 원소를 반으로 분할해서 찾는 방법이다. 시간복잡도는 O(logN) 으로 전체탐색 O(N) 보다 빠르다.
이진탐색의 조건
- 정렬이 되어있어야 한다.
이진탐색 동작방식
- 배열의 중간 값을 가져와서 찾으려고 하는 값과 비교를한다.
- 중간값과 같다면 내가 원하던 값 이니 종료하고 크면 중간값기준 오른쪽 원소들을 대상으로 탐색한다.
작으면 왼쪽 대상들을 탐색한다.
구현
public class 이진탐색 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = { 1, 7, 16, 25, 30, 33, 41, 66, 78, 90 };
int num = 78; // 우리가 찾고 싶은 숫자
int lowIndex = 0;
int highIndex = arr.length - 1;
while (true) {
int centerIndex = (lowIndex + highIndex) / 2;
if (arr[centerIndex] == num) {
System.out.println(num + "은 " + centerIndex + "번째 숫자입니다.");
break;
}
else if(arr[centerIndex]<num) {
lowIndex = centerIndex+1;
}
else { //arr[centerIndex]>num
highIndex = centerIndex-1;
}
}
}
