이진탐색은 이분탐색의 일종으로, 정렬된 범위 내에서 원하는 값을 찾는 것이다.

* 이진탐색과 이분탐색(1)

이진탐색(binary search) : 이분탐색의 일종으로, 정렬된 범위 내에서 원하는 값 찾기

이분탐색(parametric search) : 탐색범위를 두 부분으로 분할하여 원하는 값 찾기

이진탐색

이진탐색을 구현하는 방법은 2가지로 나눌 수 있다.

  1. 찾는 값이 여러개일 경우 높은 인텍스 출력
  2. 찾는 값이 여러개일 경우 낮은 인덱스 출력

예를들어 정렬된 배열 1 2 3 3 3 4 5 6 에서 3을 찾는다 하자. 이진탐색1 1번의 경우 upper_bound, 2번의 경우 lower_bound라 할때 결과는 다음과 같다. 이진탐색2

먼저 upper_bound를 구현해보자. 인자로 졍렬된 배열 array, 찾고싶은 값 k, 인덱스의 시작lo와 끝값hi을 넣어준다. while문을 돌면서 lo가 hi와 같거나 커지기 전까지 lo 또는 hi를 움직이면서 범위를 줄여나간다. upper_bound는 같은 값이 있어도 제일 큰 인덱스를 반환해야 하므로 k보다 큰값이 나오기 전까지 lo를 옮겨 오른쪽을 계속 탐색하게 한다.

public static int upper_bound(int[] array,int k,int lo,int hi) {
        int mid;
        while(lo<hi) {
            mid = (lo+hi)/2;
            if(array[mid]<=k) lo = mid+1; //k와 같은 값이 나오면 오른쪽으로 이동
            else hi = mid;
        }
        return lo;
    }

lower_bound도 같은 방식으로 구현한다. upper_bound와 차이점은 lower_bound는 k와 같은 값이 나와도 왼쪽으로 이동하여 k보다 작은값이 나올때까지 탐색한다.

public static int lower_bound(int[] array,int k, int lo,int hi) {
        int mid;
        while(lo<hi) {
            mid = (lo+hi)/2;
            if(array[mid]<k) lo = mid+1;    
            else hi = mid; //k보다 크거나 같으면 왼쪽으로 이동
        }
        return lo;
    }

전체코드:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class 이분탐색 {

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());    //arr의 길이
        int arr[] = new int[n];                     //정렬된 배열
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++)
            arr[i] = Integer.parseInt(st.nextToken());
        int input = Integer.parseInt(br.readLine());//찾고싶은 값
        bw.write("upper_bound : "+upper_bound(arr,input,0,arr.length));
        bw.write("\n");
        bw.write("lower_bound : "+lower_bound(arr,input,0,arr.length));
        bw.close();
    }
    /*
    * array - 정렬된 배열
    * k - 찾고자 하는 값
    * lo - 범위 내 제일 낮은 인덱스
    * hi - 범위 내 제일 높은 인덱스
    * */
    //정렬된 배열 array에서 k가 들어갈 수 있는 인덱스 중 높은 인덱스 반환
    public static int upper_bound(int[] array,int k,int lo,int hi) {
        int mid;
        while(lo<hi) {
            mid = (lo+hi)/2;
            if(array[mid]<=k) lo = mid+1; //k와 같은 값이 나오면 오른쪽으로 이동
            else hi = mid;
        }
        return lo;
    }
    //정렬된 배열 array에서 k가 들어갈 수 있는 인덱스 중 낮은 인덱스 반환
    public static int lower_bound(int[] array,int k, int lo,int hi) {
        int mid;
        while(lo<hi) {
            mid = (lo+hi)/2;
            if(array[mid]<k) lo = mid+1; //k보다 크거나 같으면 왼쪽으로 이동
            else hi = mid;
        }
        return lo;
    }
}

결과 : 이진탐색3

이진탐색을 직접 구현해봤으니 다음 장에선 이분탐색을 활용한 알고리즘 문제를 풀어보자!