바이너리 서치(이진 탐색)

현업에서도 많이 사용하고 있는 이진 탐색 알고리즘을 포스팅 하려고 한다.

이진 탐색을 사용하려면 기본적으로 데이터가 정렬되어 있어야 알고리즘을 사용할 수 있다.

binarySearchAsc 함수는 오름차순으로 정렬되어 있는 데이터, binarySearchDesc 함수는 내림차순으로 정렬되어 있는 데이터를 이진탐색하는 함수이다.

package sort;

import java.util.ArrayList;

public class BinarySearch
{
    public static void main(String [] args)
    {
        int[] data = new int[]{11, 12, 13, 18, 19, 20, 25, 29, 30, 36};
        int[] reverseData = reverseArray(data);
        for (int i = 0; i < data.length; i++)
        {
            System.out.println(binarySearchAsc(data, data[i]));
            System.out.println(binarySearchDesc(reverseData, reverseData[i]));
        }
    }

    private static int[] reverseArray(int [] data)
    {
        int [] result = new int[data.length];

        int j = 0;
        for (int i = data.length-1; i >= 0; i--)
        {
            result[j] = data[i];
            j++;
        }
        return result;
    }

    private static int binarySearchAsc(int [] data, int value)
    {
        int start = 0;
        int end = data.length-1;
        int mid = 0;

        while (start <= end)
        {
            mid = (start + end)/2;
            if (data[mid] == value)
            {
                return mid;
            }
            else if (data[mid] < value)
            {
                start = mid+1;
            }
            else if(data[mid] > value)
            {
                end = mid-1;
            }
        }
        return -1;
    }

    private static int binarySearchDesc(int [] data, int value)
    {
        int start = 0;
        int end = data.length-1;
        int mid = 0;

        while (start <= end)
        {
            mid = (start + end)/2;
            if (data[mid] == value)
            {
                return mid;
            }
            else if (data[mid] > value)
            {
                start = mid+1;
            }
            else if(data[mid] < value)
            {
                end = mid-1;
            }
        }
        return -1;
    }
}

 

이를 잘 활용하면 객체 리스트들의 인덱스 값을 빠르게 가지고 올 수 있다.

package sort;

import java.util.ArrayList;

public class BinarySearch
{
    public static void main(String [] args)
    {
        ArrayList<MyData> arrData = new ArrayList<>();
        for (int i = 0; i < 20; i++)
        {
            arrData.add(new MyData(i, String.valueOf(i << i)));
        }

        int position = getListPosition(arrData, 8);
        System.out.println(arrData);
        System.out.println(position == 8);
    }


    private static int getListPosition(ArrayList<MyData> arrData, int seq)
    {
        int start = 0;
        int end = arrData.size()-1;
        int mid = 0;

        while (start <= end)
        {
            mid = (start + end)/2;
            if (arrData.get(mid).seq == seq)
            {
                return mid;
            }
            else if (arrData.get(mid).seq < seq)
            {
                start = mid+1;
            }
            else if(arrData.get(mid).seq > seq)
            {
                end = mid-1;
            }
        }
        return -1;
    }

    static class MyData
    {
        int seq = 0;
        String hash = "";

        public MyData(int seq, String hash)
        {
            this.seq = seq;
            this.hash = hash;
        }

        @Override
        public String toString() {
            return "MyData{" +
                    "seq=" + seq +
                    ", hash='" + hash + '\'' +
                    '}';
        }
    }
}