Arrays are ubiquitous in software development. "Smart" data types in modern programming languages, such as, for example, dynamic arrays, provide great opportunities for convenient work with objects. But the algorithms underlying these types of data were developed in the early days of computer science, in the mid-twentieth century. The first binary search algorithm was published in 1946.
Let's consider the most popular algorithms for working with arrays.
Sequential (linear) search
This is the simplest algorithm for finding a value in an array. Uses the method of comparing array elements one by one with the key value. It is usually done from left to right. It is used if there are few elements in the array or the list is not ordered. Absolutely inefficient in large arrays, where binary search is usually used. The algorithm works as follows:
- Compare the value of the key with the value of the array element.
- If the values are equal, return the resulting value.
- If not, increase the value of the loop variable byone and compare with the next array element.
Index-sequential search
A more efficient way to look up a value in a sorted array. But more demanding on resources.
Binary search
Binary (binary) search is an algorithm for finding an element of an array by sequentially dividing the array in half and comparing the original number with the number from the middle of the array. If the number from the middle is less than the desired one, we search further, in the second part, if more, we continue the search in the first. The algorithm is the fastest of all listed and works as follows:
- First, let's find out the value of the object in the middle of the array. Checking for compliance with the original value.
- If the value from the middle is less than the original one, then we continue the search in the second half, if it is more, we search in the first.
- In the resulting half, we do the same: divide it by half and compare the resulting value.
Search occurs until the initial value becomes equal to the value in the array. If this does not happen, then this value is not in the array.
There are several pitfalls that can be encountered when designing a binary search.
Overflow of selected data type
To find the value in the middle of the array, add the right and left values and divide by two. That is:
Middle of array=Left value + (Left value - Right value)/2
Here isdanger of data type overflow during addition operation. If there are values of such large sizes in the array, you have to use various tricks to avoid risk. The following are common mistakes when developing a binary search.
Value errors
Or errors per unit. It is very important to consider the following options:
- Empty array.
- No value.
- Out of array bounds.
Multiple copies
It is necessary to take into account that if there are several identical instances of the key in the array, the program must find a certain one (the first, last, following it).
Let's analyze the implementation of this algorithm in the programming language C plus plus. Be aware that binary search only works with a sorted array! If the array is not pre-sorted, then the calculation result will be incorrect.
Below is the C++ code. First, an array of integer variables arr is initialized, with a size of ten. Next, the cin statement in the for loop waits for ten inputs from the user (line ten).
On the twentieth line, the program waits for the user to enter a key value.
Lines 29 - 35 are the implemented binary search algorithm. During the execution of the program, the value of the middle element is written to the mid variable according to the formula:
Middle of array (mid)=(Left value (l) + Right value (r))/2
Line
arr[mid]==key
Check if the midpoint is equalvalue to the key value. If equal, then the value of the flag variable is changed to TRUE, that is, the problem is solved.
If the middle value is greater than the value of our key, then the right side (variable r) is assigned to mid. Otherwise, mid is placed in r.
The last one is checking the boolean variable flag.
Advantages of binary search
Binary search should be used if you need a fast program. And writing such an algorithm will not be difficult even for a novice programmer. But it is very important to take into account all edge cases: array overflow, missing value, data overflow error.
Flaws
For the correct operation of the algorithm, the array must first be sorted. To do this, in the C ++ programming language, you can use the ready-made sort () function. And one more important point that you need to pay attention to when studying binary search in C and C ++. This algorithm can only be used with certain data structures. For example, structures using linked lists will not work here.
