Binary Search - Tìm kiếm nhị phân trong C++

| Yêu cầu

Cho mảng một chiều các số nguyên tăng dần và giá trị X cần tìm. Viết chương trình  giá trị x trong mảng, yêu cầu in ra từng bước thực hiện. Ví dụ:

| Code

Prototype

void Input(int[], int&);

void Output(int[], int);

void BinarySearch(int[], int, int);

Hàm nhập

void Input(int A[], int& n)

{

      cout << "\nNhap N: ";

      cin >> n;

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

      {

            cout << "\tNhap A[" << i << "]= ";

            cin >> A[i];

      }

}

Hàm xuất

void Output(int A[], int n)

{

      cout << "Xuat mang:\n";

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

      {

            cout << "\tA[" << i << "]= " << A[i] << endl;

      }

}

Thuật toán Binary Search

void BinarySearch(int A[], int n, int x)

{

      int i = 1;

      int l = 0, r = n - 1;

      int m;

      while (l <= r)

      {

            m = (l + r) / 2;

            cout << "Iter " << i << ": l = " << l << ", r = " << r << ", mid = " << m << ". ";

            if (x == A[m])

            {

                  //return m;

                  cout << "A key is found with the index " << m << endl;

                  break;

            }

            if (x < A[m])

            {

                  cout << "Since " << x << " is less than " << A[m] << ", continue to search left." << endl;

                  r = m - 1;

            }

            else

            {

                  cout << "Since " << x << " is greater than " << A[m] << ", continue to search right." << endl;

                  l = m + 1;

            }

            i++;

      }

      if (l>r)

      {

            cout << "Iter " << i << ": l = " << l << ", r = " << r << ", mid = " << m << ". ";

            cout << "No match. Search is finished." << endl;

            //return -1;

      }

}

Main.cpp

#include <iostream>

using namespace std;

#define MAX 100

int main()

{

      int A[MAX];

      int n, x;

      Input(A, n);

      Output(A, n);

      cout << "\nSearch: ";

      cin >> x;

      BinarySearch(A, n, x);

      system("pause");

      return 0;

}