알고리즘 : 이진탐색
입력 : 시이퀀스 {a0, a1, a2, ..., an-1} 와 목표 값 x
출력 : 인덱스 값 i
선조건 : 시이퀀스는 정렬되어 있음, 즉 a0 <= a1 <= a2 <= ... <= an-1
후조건 : ai = x; 또는 모든 j<p 에 대해서 aj<x 이고 모든 j>=p 에 대해서 aj>x 일 때 i=-p-1
1. p=0, q=n-1로 놓음.
2. p<=q 이면 단계 2-5를 반복.
3. i=(p+q)/2로 놓음.
4. ai = x 이면, i를 리턴.
5. ai<x 이면, p=i+1로 놓음; 그렇지 않으면 q=i-1로 놓음.
6. -p-1을 리턴.
Java구현
입력 : 시이퀀스 {a0, a1, a2, ..., an-1} 와 목표 값 x
출력 : 인덱스 값 i
선조건 : 시이퀀스는 정렬되어 있음, 즉 a0 <= a1 <= a2 <= ... <= an-1
후조건 : ai = x; 또는 모든 j<p 에 대해서 aj<x 이고 모든 j>=p 에 대해서 aj>x 일 때 i=-p-1
1. p=0, q=n-1로 놓음.
2. p<=q 이면 단계 2-5를 반복.
3. i=(p+q)/2로 놓음.
4. ai = x 이면, i를 리턴.
5. ai<x 이면, p=i+1로 놓음; 그렇지 않으면 q=i-1로 놓음.
6. -p-1을 리턴.
Java구현
public class BinarySearch {
// 입력값 : arr : 정렬된 정수배열, x : 찾고자 하는 값
// 출력값 : x가 존재하는 배열 인덱스, otherwise 음수값
public static int search(int[] arr, int x)
{
int i;
int p = 0;
int q = arr.length -1;
while(p<=q) {
i = (p+q)/2;
if(arr[i] == x) return i;
if(arr[i] < x) p = i+1;
else q = i-1;
}
return -p-1;
}
public static void main(String [] args)
{
int[] iarr = new int[] {14, 15, 16, 22, 99, 202, 1111, 1823};
System.out.println("search 33...result : " + search(iarr, 33));
System.out.println("search 17...result : " + search(iarr, 17));
System.out.println("search 202...result : " + search(iarr, 202));
}
}
