이진탐색

#이진탐색이란?

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

 

#언제써야할까?

=>연산횟수를 줄이기 위하여 사용

=>[BOJ] 1920 수찾기에서 완전탐색을 이용하면 시간초과가 나온다

찾아야하는 배열의 길이가 길수록 값을 찾는데 시간이 오래걸린다(ex for문-O(n),2중for문-O(n²)...)

2중for문으로는 시간초과를 해결할수없다 이진탐색(O(log n)을 이용하여 연산횟수를 줄여야한다

 

#빅O표기법?, 시간복잡도는?

https://dallae7.tistory.com/41

시간복잡도 O(logN) 빅오표기법

=>이진탐색은 'O( log n)' 의 시간복잡도. 

->O( log n) =문제해결을위한 연산들이 단계마다 줄어듬.

 

#Lower Bound,Upper Bound

https://learn.microsoft.com/ko-kr/dotnet/api/system.array.getlowerbound?view=net-7.0 

Array.GetLowerBound(Int32) 메서드 (System)

https://learn.microsoft.com/ko-kr/dotnet/api/system.array.getupperbound?view=net-7.0 

Array.GetUpperBound(Int32) 메서드 (System)

#이진탐색을 식으로 옴겨보자

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp13
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse); //{1,3,5,7,9}                                                                         
            int N = arr.Length;
            int target = 3; //찾고자하는 값
            bool isTarget = false; //출력을 위한 bool
            //int index = -1;

            int low = 0;
            int high = N - 1;

            while (low < high)
            {
                int mid = (low + high) / 2; //mid값 설정
                if (arr[mid] == target) //mid 값과 target이 일치한다면? 찾았다면?
                {
                    isTarget = true;
                    //index = mid;
                    break;
                }
                if (arr[mid] > target)
                {
                    high = mid - 1; //high 값을 mid-1
                }
                else if (arr[mid] < target)
                {
                    low = mid + 1; //low값을 mid+1
                }
            }

            //결과값 출력
            if (isTarget) //=true
            {
                Console.WriteLine("target:{0}", target);
            }
            else
            {
                Console.WriteLine("no result");
            }



        }
    }
}

#입력받은 배열 arr={1,3,5,7,9} 에서 찾고싶은 값 target=3;

#mid값과 target값을 비교해가며 일치한다면(boll ->true) 출력