Arrays are commonly used 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 that underlie the work with these data types were developed at the dawn of computer science - in the middle of the twentieth century. The first binary search algorithm was published in 1946.
Consider the most popular algorithms for working with arrays.
Sequential (linear) search
This is the simplest algorithm for finding values in an array. Uses a method of alternately comparing array elements with a key value. It is carried out usually, 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 key value 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 by one and compare with the next element in the array.
Index sequential search
A more efficient way of finding a value in a sorted array. But more demanding on resources.
Binary search
Binary (binary) search is an algorithm for finding an array element 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 look further in the second part, if more - continue the search in the first. The algorithm is the fastest of all listed and works as follows:
- First we find out the value of the object in the middle of the array. Check for compliance with the original value.
- If the value from the middle is less than the initial one, then we continue the search in the second half, if more, we search in the first.
- In the resulting half, we do the same: divide it by half and compare the resulting value.
The search occurs until the initial value is 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 occur when designing a binary search.
Overflow of selected data type
To find the value in the middle of the array, you need to add the right and left values, and divide by two. I.e:
= + ( - )/2
There is a danger of data type overflow during the addition operation. If the array contains values of such large sizes, you have to use various techniques to avoid risk. The following are standard errors when developing a binary search.
Value Errors
Or errors per unit. It is very important to consider the following options:
- An empty array.
- The value is missing.
- Going beyond the bounds of an array.
Multiple instances
It should be noted that if there are several identical copies of the key in the array, the program must find a certain one (first, last, next after it).
Let's analyze the implementations of this algorithm in the C plus plus programming language. Keep in mind that binary search only works with a sorted array! If the array is not pre-sorted, the calculation result will be incorrect.
Below is the C ++ code. First, an array of integer variables arr, size ten, is initialized. Next, the cin statement in the for loop expects ten values from the user (line ten).
In the twentieth line, the program expects the user to enter the key value.
Lines 29 - 35 are an implemented binary search algorithm. During program execution, the value of the middle element is written into the mid variable according to the formula:
(mid) = ( (l) + (r))/2
Line
arr[mid]==key
Checks if the median value is equal to the key value. If equal, then the value of the flag variable changes to TRUE, that is, the problem is solved.
If the average value is greater than the value of our key, then the right-hand side (variable r) is assigned mid. If vice versa, then mid is placed in r.
The last is checking the boolean variable flag.
Binary Search Benefits
Binary search should be used if you need fast program operation. And to write such an algorithm is not difficult even for a novice programmer. But it is very important to consider all extreme cases: going out of the array, the absence of the desired value, data overflow error.
disadvantages
For the algorithm to work correctly, the array must first be sorted. To do this, in the C ++ programming language, you can use the ready-made sort () function. And another 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.