[자료구조] (이진)이분탐색 Binary Search

이분탐색이란?

배열에서 내부의 데이터들이 정렬되어 있을 때, 혹은 정렬할 수 있는 데이터들을 가질 때 특정한 수를 찾기 위한 방법

 

1) 배열의 중간값을 변수에 할당

2) 변수와 찾으려는 값을 비교 

3)

    -1 변수가 더 크다면) 왼쪽의 데이터들의 중간값을 다시 변수에 할당

    -2 변수가 더 작다면) 오른쪽의 데이터들의 중간값을 다시 변수에 할당

 

시간복잡도

데이터가 N개인 배열에서 최악의 경우에도 시간복잡도는 O(logN)  (밑이 2)

 

코드 구현 C#

using System;
using System.IO;

namespace BinarySearch
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());

            string[] str = sr.ReadLine().Split(' ');
            int[] arr = new int[str.Length];
            for(int i = 0; i < str.Length; i++)
            {
                arr[i] = int.Parse(str[i]);
            }
            Array.Sort(arr);

            int target = int.Parse(sr.ReadLine());
            int low = 0;
            int high = arr.Length - 1;
            bool ans = false;

            while (low <= high)
            {
                int mid = (low + high) / 2;

                if (arr[mid] == target)
                {
                    ans = true;
                    break;
                }
                else if (arr[mid] > target)
                    high = mid - 1;
                else
                    low = mid + 1;
            }

            if (ans == true)
                Console.WriteLine("{0}이 존재합니다", target);
            else
                Console.WriteLine("{0}이 존재하지 않습니다.", target);

        }
    }
}

중복된 값이 있을 경우 깔끔하게 탐색하기 위해

Lower bound : 찾으려는 값보다 같거나 큰 값이 처음 나오는 위치 반환

Upper bound : 찾으려는 값보다 큰 값이 처음 나오는 위치 반환

        static void LowerBound(int[] arr, int target)
        {
            int low = 0;
            int high = arr.Length - 1;

            while (low < high)
            {
                int mid = (low + high) / 2;

                if (arr[mid] >= target)
                    high = mid;
                else
                    low = mid + 1;
            }

            if (high > arr.Length - 1)
            {
                Console.WriteLine("lowerBound : {0}", high);
            }
        }
        static void UpperBound(int[] arr, int target)
        {
            int low = 0;
            int high = arr.Length - 1;

            while (low < high)
            {
                int mid = (low + high) / 2;

                if (arr[mid] > target)
                    high = mid;
                else
                    low = mid + 1;
            }

            if (high > arr.Length - 1)
            {
                Console.WriteLine("upperBound : {0}", high);
            }
        }