using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Thuật toán tìm kiếm nhị phân (Binary Search)");

        int n, first, middle, last, key;

        int [] a;

        bool found = false;

        Console.WriteLine("Nhập vào số phần tử mảng:");

        n = int.Parse(Console.ReadLine());

        //Khởi tạo mảng

        a = new int[n];

        //Nhập dữ liệu cho từng phần tử mảng, chỉ số mảng bắt đầu từ 0

        for(int i=0; i<n; i++)

        {

            Console.Write("a[{0}]:",i);

            a[i] = int.Parse(Console.ReadLine());

        }

        Console.WriteLine("Nhập vào giá trị tìm kiếm:");

        key = int.Parse(Console.ReadLine());

        //Thuật toán

        first = 0;

        last = n - 1;

        while(first <= last)

        {

            middle = (first + last)/2;

            //Console.WriteLine("Vị trí giữa: {0}",middle);

            if(a[middle] < key)

                first = middle +1;

            else if(a[middle] == key)

            {

                Console.WriteLine("Tìm giá trị {0} ở vị trí {1} trong mảng",key,(middle+1));

                found = true;

                break;

            }

            else

                last = middle - 1;

            //Console.WriteLine("First: {0}, Last: {1}", middle, last);

        }

        if (found == false)

            Console.WriteLine("Không tìm thấy giá trị tìm kiếm");

    }

}