Binary Search (iterative)

1. Problem

- 정렬된 배열에서 x를 찾아보자

 

2. Input

1) 양수 n

2) 오름차순으로 정렬된 배열 S indexed from 1 to n

3) key x

 

3. Output

1) x의 위치

2) x가 없다면 0을 반환

 

4. PseudoCode

index binsearch(int n, const keytype S[], keytype x, index location){
    index low, high, mid;
    low = 1; high = n; location = 0;
    while(low<=high && location==0){
        mid = floor((low+high)/2);
        if(x==S[mid])
            location = mid;
        else if(x<S[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return location;
}

 

5. Example

class Test {
    public static void main(String[] args){
    	int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    	int a = 7;
    	System.out.println(a + "의 위치: " + binsearch(arr.length, arr, a)); // 7의 위치: 7
    }
    
    static int binsearch(int n, int[] S, int x){
        int low=0, high=n-1, mid, location = 0;
        while(low<=high && location==0){
            mid = (low+high)/2;
            if(x==S[mid])
                location = mid;
            else if(x<S[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        return location+1;
    }
}