using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/// <summary>
/// 이진 탐색, 이분 검색, Binary search
/// 오름차순으로 미리 정렬이 되어 있는 데이터를 이진검색을 사용하여 
/// 반씩 나눠서 검색하기
/// </summary>
public class Program
{

    public static void Main()
    {

        //[1] Input
        int[] data = { 1, 3, 5, 7, 9 }; //정렬이 이미 되어 있어야 함(오름차순)
        int N = data.Length;//의사코드
        int search = 3;
        bool flag = false; //플래그 변수: 찾으면 true, 찾지못하면 false
        int index = -1; //인덱스 변수: 찾은 위치

        //[2] Process
        int low = 0; //min: 낮은 인덱스
        int high = N-1; //max: 높은 인덱스

        while(low<= high)
        {
            int mid = (low+high)/2; //중간 인덱스 구하기
            if(data[mid] == search)
            {
                flag = true; index = mid; break;//찾으면 플래그, 인덱스 저장 후 종료
            }

            if (data[mid]> search)
            {
                high = mid - 1; //찾을 데이터가 작으면 왼쪽 영역으로 이동
            }
            else
            {
                low = mid + 1; //찾을 데이터가 크면 오른쪽 영역으로 이동
            }

        }     

        //[3] Output
        if (flag)
        {
            Console.WriteLine($"{search}을(를) {index}위치에서 찾았습니다.");
        }
        else
        {
            Console.WriteLine("찾지 못했습니다.");
        }
       
    }
}

/*int[] data = { 1, 3, 5, 7, 9 };
var result = data.ToList().BinarySearch(9);
result
4*/

/*if (Array.BinarySearch(data, 3) >= 0)
{
    Console.WriteLine($"{3}-{Array.BinarySearch(data, 3)}");
}
3 - 1
if (Array.BinarySearch(data, 11) >= 0)
{
    Console.WriteLine($"{3}-{Array.BinarySearch(data, 3)}");
}
*/