Binary search of an array algorithm in C/C++

Previous
|< Sorting arrays

Let's see first what the problem is with searching for an element in the observed array

Let's give a set of n elements. For example, let n = 10;
int A[10] = {2, 3, -1, 4, 6, 33, 12, 4, 5, 6, 8}

Set the following problem: Make sure the array contains element 33.
This can be done by passing through all the elements of a sequence in sequence through cycles, whether the current element is equal to 33. If found, we interrupt the cycle.

Figure 1: Binary search algorithm

bool found=false;
for(int i = 0; i < n; i++)
{
if(A[ i ]==33)
{
found=true;
break;
}
}

This is a way that represents a LINEAR SEARCH of an array.

In the event that there is no required element in the array, it will do as many iterations as n. In this case, it's "only" n times. The question is, what if the number of elements of the series is much higher. The code execution time would be too long. It would be a more efficient way to use it: BINARY SEARCH.

BINARY SEARCH OF AN ARRAY ALGORITHM

Suppose a array of n elements V [n] is loaded.
The array must be arranged (sorted). If it is not the first it must sort.
-
We check that X is in the array. The algorithm consists in passing through the loop to check that the required element is equal to the middle element.
If yes, it was found and the search ends. If the requested element X is smaller than the middle element of the verified sequence S then it is in the left half of the array, and if it is larger then the right one. In the next iteration, we check only the one half of the array in which the required element can be found. So the upper limit for checking is the previous mean value of the array. This procedure is repeated until we find the required element.

Do you want to understand how quickly you can sort an array? See description and animation for quick sort algorithm!

Figure 2: Binary search of an array - algorithm

/* We search the interval[l, d] */
int l = 0;
int d = n-1;
/* As long as the interval [l, d] is not empty */
while (l <= d)
{
/*Middle interval position [l, d]*/
int s = (l+d)/2;
/*We examine the relation of x and the middle element a[s]*/
if (x == a[s])
/* The element was found */
return s;
else if (x < a[s])
{
/* We search the interval[l, s-1] */
d = s-1;
}
else
{
/* We search the interval [s+1, d] */
l = s+1;
}
}

Example 1:
Write a program that inputs from the standard input using the scanf function with no more than 20 characters and checks if the string contains the @

Task is solved using Linear search:

#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int main()
{
    char a[21];
    scanf("%s",&a);
    bool discovered=false;
    int pos=0;
    for(int i=0; i<strlen(a); i++){
        if(a[i]=='@'){
            discovered=true;
            pos=i;
            break;
        }

    }
    if(discovered){
        printf("Character @ is on the position %d",pos);
    }
    else{
        printf("Character is not found");
    }
    return 0;
}

Here, a char character string is used, which is loaded using the scanf function. A set of character here does not have to be edited as opposed to a binary search that requires a string to be sorted. Note that the string length is obtained by using the standard function strlen from the standard header <string.h>

Example 2:

Write a program that inputs from a standard input using the scanf lexicographic edited shortcut function with no more than 20 characters and checks if the low contains the @ sign. Task to do using binary search

Solution: Assume that the low character entered in the lexical order is entered. If it was not, then we would have to do it first.
We use the binary search algorithm described above, to determine whether the character 'q' exists, and if there is a position at which it is.

#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int main()
{
char a[21], x;
scanf("%s", &a);
bool found=false;
int pos=0;
x='q';
int n=strlen(a);
/* We search the interval[l, d] */
int l=0,d=n-1;
/* As long as the interval [l, d] is not empty */
while(l<=d){
/* Mean interval position [l, d]*/
int s=(l+d)/2;
if (x==a[s]){
/* The element was found*/
pos=s;
found= true;
break;
}
else if(x<a[s]){
/* We search the interval [l, s-1] */
d=s-1;
}
else{
/* We search the interval [s+1, d] */
l=s+1;
}
}
if(found){
printf("Character @ is in position %d", pos);
}
else{
printf("character not found");
}
return 0;
}

Example 3: Height difference

Note: This example is taken from a website: dms.rs/informatika-osnovne-skole/

In a school, actors are chosen for the school play in which the characters they play they have a big difference in height. Write a program that determines how many ways we can select two actors from the class so that their height difference is equal given number dif.
Input:
From the standard input, a positive natural number dif(1 ≤ dif ≤ 1000) is entered first, in in the next row number of students 𝑛 (1 ≤ 𝑛 ≤ 50000), and after that in the next n rows the height of each student (a number between 1 and 100000).
Output:
Print the number of pairs that can be formed to the standard output.
Example 1
Input
10
5
150
160
165
170
175
Output
3
It is possible to make pairs from the first and second child (150, 160), from the second and fourth child (160, 170) and the third and fifth child (165, 175).

Example 2
Input
23
5
157
180
157
162
134
Output
4
It is possible to make pairs from the first and second child (157, 180), from the fifth and first (134, 157), from the second and third (157, 180) and from the fifth and third child (134, 157).
Note
In 20 out of 25 test examples, all children will be different heights.

Task analysis

If the heights are loaded as an array, it should be sorted first. In order to make all combinations of pairs and compare the height difference of those pairs with the given one, on the one hand, you need to change the first element of the sequence, i.e. the height of the first child within the pair, and on the other hand, for the fixed value of the first height, change the second value in the pair. Two loops can be used for this, one nested inside the other. Both loops can change values linearly, from beginning to end, or one linearly, while the other Binary Search, which would be more efficient.

Instructions for solving the task

Solve the task according to the following algorithm:

Enter two integers, the required difference and the number of children.
Load an array of child heights
Open two loops, one nested inside the other
Sort the array in ascending order.
Form the height difference in the loop and compare it with the given one.
If the difference is equal to the given one, increase the required number of pairs by 1
The inner loop changes the second height by looking for the one whose difference with the first height is equal to the given one. Search using the binary search algorithm. Therefore, change the far left and far right positions of the observed subarray.
This subarray is initially equal to the whole array, which means that the far left and far right positions are initially the bottom positions of the whole array.
Inside the cycle, the middle position is first determined .Then the difference of the array element at that, middle position and the height of the first child within the current pair is found. If that difference is exactly the one given, the number of found pairs increases by 1.
It should be checked if there are other values with the same difference, e.g. if there are more children with the same height.
If not, then further check whether the requested difference is in the left or right half of the current array and accordingly move the rightmost or leftmost position of the array in the next cycle.
After exiting the loop, print the required number of pairs

Solution for task

#include < iostream >
#include< algorithm >
using namespace std;
int main()
{

int dif,n,b=0;
cin >> dif >> n;//dif-difference for search,n-number of childern
int v[n]; //the heights array
//Enter heights of childern
for(int i=0; i < n; i++)
{

cin >> v[i];

}
/*Sorting the heights array */
sort(v,v+n);
/*Form differnt pair of height and thier analyse */
for(int i=0; i < n-1; i++)
{

int l=i+1,r=n-1;//the array for search is changed from i+1 to n-1, l-left,r-right
while(l <= r)//the cycle continues as long as the left position is less than or equal to the right position
{

int mid=(l+r)/2;//middle position of interval [l,r]
int raz=v[mid]-v[i];//height difference
/*If the difference is equal to diff, a new pair is found whose height difference is equal to the given one*/
if(raz==dif)
{

b++;//inkrement number of pairs
int k=mid+1;
while(v[k]==v[mid])
{

b++;
k++;

}
k=mid-1;
while(v[k]==v[mid])
{

b++;
k--;

}
break;

}
else if(dif {

r=mid-1; /*the right limit for a new search is the first position to the left of the middle position*/

}
else if(dif > raz)/*If the expected difference is greather than the actual difference, the expected value is on the right side of the observed substring*/
{

l=mid+1;/*the left limit for a new search is the first position to the right of the middle position*/

}

}
cout << b << endl;
return 0;

}