//chương trình c++ tìm kiếm nhị phân cho mảng M gồm n phần tử viết chương trình in ra số lần chia đôi dãy và các khoảng chứa giá trị X cần tìm trong mỗi lần chia đôi mảng của giải thuật tìm kiếm nhị phân
vd mảng M : 2 3 5 6 8 9 11
tìm x =2
chương trình phải in ra là:
số lần chia đôi mảng là: 2
lần 1: x =2 nằm trong đoạn[0..2]//mid = 3
lần 2: x=2 nằm trong đoạn [0..0]// mid =1
khi X = mid thì ngừng chia mảng//

#include<iostream>
#include<iomanip>
using namespace std;
#define Max 100
// khai bao ham con
void nhapmangM(int arrA[], int nN);
void xuatmangM(int arr[], int nN);
int binarySearch(int arrA[], int nN, int nKey,int &nDem);
// chuong trinh chinh
void main()
{
int arrA[Max];
int nN, nKey, nDem = 0;
cout << "nhap so luong phan tu trong mang\n";
cin >> nN;
nhapmangM(arrA, nN);
cout << "\n xuat mang\n";
xuatmangM(arrA, nN);
cout << "nhap vao gia tri X can tim trong mang\n:";
cin >> nKey;
binarySearch(arrA, nN, nKey, nDem);
cout << "\nso lan chia doi mang la :" << nDem << endl;
system("pause");
}
// dinh nghia ham con
int binarySearch(int arrA[], int nN, int nKey,int &nDem)
{
int nLeft = 0,nRight = nN - 1, nMid;
while (nLeft <= nRight)
{
nMid = (nLeft + nRight) / 2;
nDem++;
for (int i = 1; i <= nDem; i++)
{
cout << "\nlan :" << i;
if (arrA[nMid] == nKey)
{
cout << "\nX chinh la Mid\n";
return nMid;
}
else if (arrA[nMid] < nKey)
{
cout << "\nX = " << nKey << " nam trong doan:\n";
nLeft = nMid + 1;
cout << "[" << nLeft <<".." << nRight << "]";
}
else
{
nRight = nMid - 1;
cout << "\nX = " << nKey << " nam trong doan:\n";
cout << "[" << nLeft << ".." << nRight << "]";
}
}
}
return -1;
}
void xuatmangM(int arr[], int nN)
{
for (int i = 0; i < nN; i++)
{
cout << arr[i] << " ";
}
}
void nhapmangM(int arrA[], int nN)
{
for (int i = 0; i < nN; i++)
{
cout << "arrA[" << i << "]=";
cin >> arrA[i];
}
}