이분탐색 과 Lower Bound , Upper Bound (상/하한선)

이진 탐색이란 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다.

이진 탐색은 배열의 중간을 기준으로 데이터를 탐색하기 때문에 반드시 데이터가 정렬된 상태로 존재해야 한다.  

 

이진 탐색의 시간 복잡도는 O(logN)으로 배열을 전수 조사하는 O(N)에 비하면 상대적으로 빠른 탐색 알고리즘에 속한다. O(logN)만에 값을 찾을 수 있는 이유는 중간을 기준으로 탐색 대상을 절반씩 줄여나가기 때문이다.

 

using System;
using System.IO;
using System.Text;

namespace Assignment01
{
    class Program
    {
        static void Main(string[] args)
        {   
            StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            int[] arr = { 3, 4, 2, 6, 9, 1 };
            
            Array.Sort(arr);

            int left = 0;
            int right = arr.Length - 1;
            int mid = 0;
            int num = 7;
            bool ans = false; 
            while (left < right)
            {
                mid = (left + right) / 2;
                if (arr[mid] == num)
                {
                    ans = true;
                    break;;
                }else if (arr[mid] > num)   //중앙 값이 찾고자 하는 값보다 크다면 
                {
                    left = mid + 1;
                }
                else
                {
                    //중앙 값이 찾고자 하는 값보다 작다면 
                    right = mid - 1;
                }
            }
            
            Console.WriteLine(ans);

            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}

 

중복된 배열에서의 이진 탐색

이진 탐색의 입력값이 중복값 없는 깔끔한 배열이라고 보장할 수 없다.

그러므로 중복된 원소가 존재할 경우 어떻게 탐색을 해야 하는지 고민해야 한다.

 

 

• Lower bound는 데이터 내에서 특정 값보다 같거나 큰 값이 처음 나오는 위치를 리턴해준다.
• High Bound는 특정 값보다 처음으로 큰 값이나 나오는 위치를 리턴해준다.

 

lower bound : 찾는 값과 같거나 큰 값이 있는 index 반환 

upper bound : 찾는 값보다 처음으로 큰 값이 있는 index 반환 

 

using System;
using System.IO;
using System.IO.Pipes;
using System.Text;

namespace Assignment01
{
    class Program
    {
        static void Main(string[] args)
        {   
            // StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            // StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            Console.WriteLine("index: {0}", LowerBound(new int[] { 1, 2, 2, 3, 3, 3, 4, 6, 7 }, 0));
            Console.WriteLine("index: {0}", UpperBound(new int[] { 1, 2, 2, 3, 3, 3, 4, 6, 7 }, 0));
            

            // sr.Close();
            // sw.Flush();
            // sw.Close();
        }

        static int BinarySearch(int[] arr, int num)
        {
            Array.Sort(arr);
            
            //print sorted array 
            for(int i = 0; i<arr.Length;i++)
                Console.Write("{0} ", arr[i]);
            Console.WriteLine();
            
            Console.WriteLine("search num : {0}", num);
            
            int left = 0;
            int right = arr.Length - 1;
            int mid = 0;
            int cnt = 0;
            while (left < right)
            {
                cnt++;
                mid = (left + right) / 2;
                if (num == arr[mid])
                {
                    return mid;
                }else if (num < arr[mid])    
                {
                    left = mid + 1;
                }
                else
                { 
                    right = mid - 1;
                }
            }
            
            return -1;
        }

        //lower bound 는 찾는 값과 같거나 큰 값이 나오는 처음 index를 반환  
        static int LowerBound(int[] arr, int num)
        {
            Array.Sort(arr);
            
            //print sorted array 
            for(int i = 0; i<arr.Length;i++)
                Console.Write("{0} ", arr[i]);
            Console.WriteLine();
            
            Console.WriteLine("search num : {0}", num);
            
            int left = 0;
            int right = arr.Length;
            int mid = 0;
            while (left < right)
            {
                mid = (left + right) / 2;
                if (num <= arr[mid])
                {
                    right = mid;
                }
                else
                {
                    left = mid + 1;
                }
            }

            return (left > arr.Length-1) ? -1 : left;
        }

        //UpperBound: 찾는값보다 처음으로 큰 값이 나오는 index를 반환  
        static int UpperBound(int[] arr, int num)
        {
            Array.Sort(arr);
            
            //print sorted array 
            for(int i = 0; i<arr.Length;i++)
                Console.Write("{0} ", arr[i]);
            Console.WriteLine();
            
            Console.WriteLine("search num : {0}", num);
            
            int left = 0;
            int right = arr.Length;
            int mid = 0;
            bool ans = false;
            while (left < right)
            {
                mid = (left + right) / 2;
                
                if (num < arr[mid])    
                {
                    right = mid;
                }
                else 
                {
                    left = mid + 1;   
                }
                
                
            }
            
            return (left > arr.Length-1) ? -1 : left;
        }
    }
}

 

 

lower bound : 찾는 값과 같거나 큰 값이 있는 index 반환

while (left < right)
{
    mid = (left + right) / 2;
    
    if (num <= arr[mid])
    {
        right = mid;
    }
    else
    {
        left = mid + 1;
    }
}

 

upper bound : 찾는 값보다 처음으로 큰 값이 있는 index 반환 

while (left < right)
{
    mid = (left + right) / 2;
    
    if (num < arr[mid])    
    {
        right = mid;
    }
    else 
    {
        left = mid + 1;   
    }    
}

 

 

lower : <= 

upper : <