Binary Search Basic

 This Problem was introduced on the BackJoon Algorithm Website.

Problem : 

There are many algorithms for searching numbers. 

Today I want to use Binary search to find an item from a sorted list.

This algorithm allows us to find a number in log(N) time in the worst case (N is the size of the input or the item list).

Binary search is a simple and also powerful algorithm for searching numbers from a sorted list or array. 

Here is a simple rule of Binary Search:

1. Set the mid element of the array as a key.

2. If what you are looking for is equal to the value of the array at a key index then you found a number and its index!

3. Or if the value of the key is less than the item in the middle of the interval, narrow the interval to the lower half.

4. Or narrow it to the upper half.

5. Repeatedly check from the second point until the value is found or the interval is empty.

"From GeeksforGeeks"

In this question, I had to find more than one number, which means I had to just simply repeat the upper process.

The C++ code for simple Binary Search is following:

/////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>

#include <math.h> 

#include <algorithm>

using namespace std;

int vecStoreAll[1000000];

int iWantedNum;

int iNumCasesCnt;

int iWantedNumCnt;

bool Search_B(int iWantedNumber, int startIdx, int endIdx) {

int midIdx = 0;

if (endIdx < startIdx) {

return 0;

}

midIdx = (endIdx + startIdx) / 2;

if (vecStoreAll[midIdx] == iWantedNumber) {

return 1;

}

if (vecStoreAll[midIdx] > iWantedNumber) {

if (Search_B(iWantedNumber, startIdx, midIdx - 1)) {

return 1;

}

}

else {

if (Search_B(iWantedNumber, midIdx + 1, endIdx)) {

return 1;

}

}

return 0;

}

int main()

{

ios_base::sync_with_stdio(0); cin.tie(0); cin >> iNumCasesCnt;

for (int i = 0; i < iNumCasesCnt; i++) {

cin >> vecStoreAll[i];

}

sort(vecStoreAll, vecStoreAll + iNumCasesCnt);

cin >> iWantedNum
Cnt;

for (int i = 0; i < iWantedNumCnt; i++) {

cin >> iWantedNum; cout << Search_B(iWantedNum, 0, iNumCasesCnt - 1) << "\n";

} 

}

####################################################################

References :

    https://www.geeksforgeeks.org/binary-search/

Problem Source: https://www.acmicpc.net/problem/1920

My Github:  https://github.com/AdvancedUno/AlgorithmProblems/tree/main/Binary_Search/Binary_Search