반응형
이진탐색 알고리즘
오름차순으로 정렬되어 있는 리스트에서 특정한 값을 찾을 때, 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식이다.
이진탐색 알고리즘 조건
★ 모든 원소는 정렬되어야 한다. ★
이진탐색 알고리즘의 장단점
장점 : 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다.
단점 : 정렬된 리스트에서만 사용할 수 있다
이진 탐색의 구현
1. 탐색의 대상이 되는 자료들이 array[low] 에서부터 array[high]에 들어있다고 가정하자. (정렬되어 있어야 함)
즉 어떤 시점에서 탐색되어야 할 범위는 low에서 high 까지가 된다.
맨 처음 low에는 0번 인덱스의 값, high에는 n-1번 인덱스의 값이 들어갈 것이다.
2. low와 high값에 의거해 중간값 mid 값은 (low + high) / 2이다.
즉, array[low] ~ array[high] 까지의 탐색은
array[low] ~ array[middle-1] + array[middle+1] + array[high]까지의 탐색이 된다.
3. array[mid] 값과 구하고자 하는 key값을 비교한다.
3-1. key > mid : 구하고자 하는 값이 중간값보다 높다면 low를 mid +1로 만들어 줌 (왼쪽 반을 버림)
3-2. key < mid : 구하고자하는 값이 중간값 보다 낮다면 high를 mid-1로 만들어 줌 (오른쪽 반을 버림)
3-3. key == mid : 구하고자 하는 값을 찾음
4. low > high 되는 교차(CROSS)상황이 발생한다면 , 해당되는 데이터가 없으므로 탐색이 종료된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
package class04;
import java.util.Scanner;
public class Test06 {
public static void main(String[] args) {
// [이진탐색(이분검색)]
// -> 탐색할 대상 배열이 "정렬"되어있어야만 합니다.
int[] data = {1,40,50,55,60,70,81,92,94,100};
Scanner sc = new Scanner(System.in);
while(true) {
boolean flag= true; // 어떠한 행위가 잘 되었는지를 체크하는 변수
// T / F 밖에 없다!
System.out.print("검색 : ");
int num = sc.nextInt();
int L=0;
int H=data.length-1;
while (true) {
int M = (L+H)/2; //
if (data[M] == num) { // 종료조건
System.out.println("["+M+"]에"+num+"가 존재합니다!");
break;
}
else if (data[M] > num) {// DOWN 상황
H=M-1;
}else { // UP 상황
L=M+1;
}
if (L>H) { // 교차(cross) 상황
System.out.println("찾는 데이터가 없습니다.");
flag=false; // 만약, 찾으려는 데이터가 없다면 F로 값을 변경
break;
}
}
if (flag) {//flag변수가 T상태를 유지하면, 멈출수있다!
// 내가 원하는 데이터를 찾은 상황 -> T
// 내가 찾으려는 데이터가 없는 상황 -> F
break;
}
}
}
}
|
cs |
반응형
'JAVA' 카테고리의 다른 글
| [JAVA] 중첩반복문 (별찍기) (0) | 2022.06.17 |
|---|---|
| [JAVA] 배열 랜덤(Random) 숫자 생성 (0) | 2022.06.16 |
| [JAVA] 배열 버블정렬(Bubble Sort) 알고리즘 (0) | 2022.06.15 |
| [JAVA] 반복문 for, while (0) | 2022.06.15 |
| [JAVA] 배열 최대값, 최소값 구하기 알고리즘 (0) | 2022.06.14 |
