Binary search on your fingers
Greetings to all readers of the publication! I am the author of the telegram channel “Notes of a Javast”and just recently I started diving into algorithms. Now I'm reading a book “Grokking Algorithms”and I plan to explain the material I have studied in simple terms.
In this article, we'll look at how arrays work, what algorithms are, and how binary search works “under the hood.” Let's get started!
Algorithms in programming
An algorithm is a sequence of actions that lead to a result. The goal of an algorithm can be anything: sorting a list of elements by a specific parameter, finding the minimum or maximum number, etc.
Example: to prepare soup, you need to perform a series of sequential actions: prepare the ingredients, boil the meat, add potatoes, fried vegetables, salt and cover with a lid to infuse.
The same set of actions exists in programming: depending on the task, we perform a very specific set of actions in a specified order, which ultimately lead to the desired result. (whether it's sorting a list of elements/finding the minimum or maximum element).
What is an array?
To dive deeper into algorithms, you need to understand how data structures work in programming.
The current topic assumes that you are already familiar with the array data structure from the inside. For those who are not familiar with arrays or are not sure that they fully understand their principle of operation in detail, I have prepared a very simple explanation with examples and illustrations:
It will be clearer using the example of a movie theater. Imagine that you are buying a movie ticket – you go to the website and see the seats available for purchase:
In this example, we are looking at seat number 1, in row 1 – for simplicity, let's designate this seat as 1×1.
Memory in the application can also be represented as a cinema hall – it is such a large, organized place in which there are places. Each such place is called a cell (memory cell)and each cell, like a seat in a movie theater, has its own address (in our example it is 1×1)Thus, all cells have their own address and some order.
It is also important to understand that memorylike a cinema hall, has its own limit – each cinema hall has a certain number of seats, just as in memory there is a certain number of these same seats (memory cells).
Some memory cells may already be occupied by some values entered by other programs or components. Actually, the same goes for like seats in a movie theater: when you arrive at the cinema you may find yourself in situationsWhen free seats at all No.
Now let's imagine that your group of 5 friends went to the cinema. It is logical that you would all want to sit together, next to each other – in this case, you would buy 5 tickets. You thought for a long time, and decided to sit in the very center, so you took 5 tickets in the 7th row:
The cells marked in gray are occupied places. Exactly the same as occupied cells in memory.
First place friend Vanya took over, number 9 row 7 – for simplicity, we will denote it as 9×7. The last among the friends was Anya – she bought a ticket for seat 13 row 7 – (let's denote it as 13×7).
In total We took 5 seats in the 7th row, from 9th to 13th place inclusive. Arrays are also arranged in the same way: when creating this data structure, we reserve n consecutive memory cells (in our example – the number of seats)Where n – any non-negative integer (in our case it is 5, since we bought 5 seats).
As an example, let's create an array of strings in Java that will store ticket numbers for all members of the company:
String[] ticketsArray = new String[]{"9x7", "10x7", "11x7", "12x7", "13x7"};
Some cinemas have it Possibility of booking seats – you can indicate that these places belong to you, but tickets not paid yetYou can pay them a little later, but they are already “tied” to you.
Also in memory: we can reserve a certain number of cells for our needs. In our example, we reserve 5 cells for an array that stores movie theater ticket numbers.
Actually, now we are getting very close to what arrays are:
Array – a data structure that stores a set of values of a certain type (you can't put data of different types into an array – if the array is declared as String[]then the values there can only be of the String type).
Key is understanding reservation mechanismthanks to which we have the ability to create an array, and also get those “goodies” that this data structure gives us.
This means that when an array is created, reservation of nearby cellslike the seats in the movie theater for a group of friends in the last example. You can't reserve 3 seats for an array that are in different parts of memory. Such restrictions allow you to take advantage of arrays – access to an element by index in constant time.
You can create an array of size n = 15, thereby reserving memory for this array (it is not necessary to fill it with values immediately) in the following way:
String[] ticketsArray = new String[15];
In this case, we are just “reserving” cells in memory – like tickets in a movie theater. Perhaps our array of size 15 will only have 1 value – but its capacity is still 15 elements, and the memory allocated for it will not disappear. (It's like renting 15 tables for your wedding guests. It's not a given that all the guests will show up, and some tables will end up empty. But it's still 15 tables that are reserved for your wedding :))
A few more important words about arrays before we move on:
An array has indices. These are pointers that allow you to access a specific element of the array.
Indexes within an array start at 0. When creating an array of size 5, the first element is numbered 0, while the last element is numbered 4. (When I first heard about this, my brain exploded trying to understand what was happening, but trust me, you will soon get used to it)
The size of the array cannot be increased. Since the allocated space is static, we allocate space for the array at the declaration stage. To increase the size, we need to create a new array and move the data from the old array there.
To understand, imagine a sheet of paper in a grid, which has 32 cells in length. Having cut a line of 20 cells, we cannot add more there. To do this, we need to cut a new line, with a larger number of cells. The same with arrays – having once allocated space for an array, you can use this range of cells. To add more, you need to create a new array with a larger size.
Due to the fact that the space allocated for the array is a continuous block of data in memory, obtaining an array element by index occurs in constant time – O(1) (that is, always in the same amount of time).
Imagine that you live in apartment 12. You need to know what number your neighbor's apartment is. It is logical that the neighbor's apartment number is 13. Arrays work the same way: knowing the cell of the beginning of the array, we can access the required array index in a fixed (constant) time. This calculation is performed by the array itself when accessing the required element. The developer only needs to specify the number of the required index!
For a better understanding of the last point, I will give a more detailed explanation:
When created, the array stores the address of the beginning. If we need to get the third element of the array, we simply access the array element at index 2. (remember that the countdown starts from 0), and “under the hood” the address of the cell containing the value we need is calculated. Knowing the address of the beginning of the array, we simply access this address + 2, and get the desired elementWe go there, take the value, and that's it!
So, to access a specific element of the array, we simply access it by index:
String[] ticketsArray = new String[]{"9x7", "10x7", "11x7", "12x7", "13x7"};
System.out.println(ticketsArray[0]);I took the same example as before as a basis: only the output of the first element was added. Now the value “9×7” will be output to the console, since we accessed the first element of the array, with the cell number 0 (as we already remember, the numbering of elements in an array starts from 0).
We've sorted out the arrays – now You can start the binary search!
Binary search
As is clear from the title, we will talk about search. We encounter it everywhere: when searching for a request in the Google search bar, or when searching for your things, numbers in your address book.
What is binary search?
Binary search – finding an element of an ordered set by dividing this set in half.
And now in simple words: the ordered (sorted) list of values is divided by 2 each time until we find the desired element.
And most importantly: binary search works only for sorted arrays!
Now let's abstract and consider a new example:
Let's imagine that we need to find a person's number in an address book. Knowing his last name, we can find his contacts in a very short time.
When we look for a word in the dictionary, or a contact in the address book, we do not look through all the entries, but start with the required letter. In this way, we cut off a large part of the book that is pointless to look through.
Let's say the last name of the contact we need is “Alekseev”. In this case, we cut off most of the dictionary, since the last name begins with the first letter of the alphabet. Next, we look at the second letter of the last name – “l”, respectively, we discard all the last names following after or before “Al”, and thus we get to the contact we need. In this approach, we do not look at all the contacts in the address book, but sequentially discard some of the contacts, which ultimately significantly simplifies and speeds up the search process.
In the same way, we can imagine guessing a number in an array of values in the range from 0 to 100. We can find the desired number by dividing by 2 at each step. (iteration).
Let's imagine that the number we are thinking of is 65. The person who thought of the number will say whether our number is the number we were thinking of, or whether it is greater or less than the number we were thinking of. The order of actions will be as follows:
We move to the middle of the array, this is the number 50. We compare the number 50 with the guessed 65 – the number 50 is smaller, which means we move on, to the right. So, we have already cut off the first 50 numbers! Thus, we have reduced the number of iterations by half!
Let's look further: our range has narrowed and consists of numbers from 51 to 100. The middle of this range = (51 + 100) / 2 = 75. Is the number 75 greater than the guessed one? – Yes. So we cut off some of the numbers after 75. By doing this, we have removed another 25 numbers that simply do not make sense to look at – we already know that they do not fit!
This division continues until our list of numbers narrows down until we hit a situation where the middle element of the array is equal to the number we've guessed, or until the range narrows down to 1 element. The number has been found, and we can rejoice!
The actions described above constitute the entire logic of binary search. Searching among other data formats, such as strings, works in the same way! If we need to find the required string in an array of strings, or the required contact by a person's last name, we simply cut off half of the list at each iteration. This approach allows us to find the required element in the array in 
operations – which means inverse squaring. That is, the logarithm is the inverse operation of raising to a power:
Implementing Binary Search in Java
Initially, I wrote the binary search myself, having understood only the idea itself. It took me about 2 hours, as I was constantly being stupid and making mistakes in the implementation.
Problem conditions for leetcode:
An array of integers is given numssorted in ascending order, and an integer search item. Write a function to find the search item in nums. If the searched for exists, return its index. Otherwise, return -1.
It is necessary to write an algorithm with the complexity of execution O(log n).
Now we will look step by step at how I thought, what mistakes I made, and how to come to the right decision:
Cycle. It is obvious that dividing an array is a repeated action. So we need a cycle through which we will go (iterate)and depending on the conditions, remove the left or right parts of the array.
Storing element boundaries in variables. To work with boundaries (left and right parts) of the arrayyou need to create variables for them and also store the index of the middle element.
Negative scenario. There may be a case where the element we are looking for is not in the array of numbers. In this case, we need to return -1, not the element index. We should limit the loop and understand that at some point we have gone through the entire array, reached the last element, but if it is not equal to the number we are looking for, return -1.
The first thing I did was – I threw in some high-level codewhich looked something like this:
public class Main {
public static void main(String[] args) {
int result = search(new int[]{1, 3, 5, 6, 9}, 99);
System.out.println(result);
}
public static int search(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
int mid = (low + high) / 2;
while (true) { // бесконечный цикл
if (target == nums[mid]) { // если искомое число равно среднему элемент массива, возвращаем индекс этого элемента
return mid;
}
if (target > nums[mid]) { // если искомое число больше, чем средний элемент массива, отбрасываем левую часть диапазона
low = mid;
mid = (low + high) / 2; // считаем новую середину массива, после того как отбросили левую часть
} else if (target < nums[mid]) { // иначе, если искомое число меньше, чем середина, отбрасываем правую часть диапазона
high = mid;
mid = (low + high) / 2; // считаем новую середину массива, после того как отбросили правую часть
} else { // иначе элемент не найден, возвращаем -1
return -1;
}
}
}
}Now let's look at the first iteration over the array:
As you can see, our goal is to find the index of element 99. There is just one problem: there is no such element here, and in this case the array should return -1. Let's run the code, and we get… Endless cycle, Karl!
Let's figure out why this is so:
1) The while condition specifies true, which means that if the required number is not present (in our example, the number 99 is not inside the array of numbers), the cycle will repeat over and over again.
2) When we enter the second condition of line 15, our element 99 is indeed greater than the middle. Then a shift should occur – if we cut off the left part, then low should equal mid + 1, since the middle element with which we compared turned out to be less than the number we need, accordingly we need to jump this middle element 1 position to the right (mid + 1). On the diagram it will look like this:
But this does not happen, as a result we enter the cycle again, get mid = 2, and so on endlessly. The middle of the array is always the same. How to fix this? Try to think for yourself, and the solution will be waiting for you in the spoiler.
Hidden text
In order to correctly calculate the new indices of the lower bound (low) and upper bound (high), it is necessary to shift them by 1 element to the left or right.
It is also necessary to introduce a limitation when executing the loop. In the case where the lower and upper ranges intersect (i.e. a situation occurs when we have gone through the entire array and found no matches – low and high will refer to the same array index), it is necessary to terminate the loop.
In code it looks like this:
public static int search(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
int mid = (low + high) / 2;
while (low <= high) { // итерируемся до тех пор, пока левая и правая часть не пересеклись
if (target == nums[mid]) {
return mid;
}
if (target > nums[mid]) {
low = mid + 1; // смещаем границу low вправо на 1 элемент
} else {
high = mid - 1; // смещаем границу high влево на 1 элемент
}
mid = (low + high) / 2; // пересчитываем середину массива после смещения диапазонов low, high
}
return -1; // искомое число не найдено
}Let's see what has changed:
1) We fixed the infinite loop with a condition low <= highwhich literally means: we iterate through the array and search for the desired number until it turns out that the pointers (low/high) point to 1 element. In this case, we have gone through the entire array and have not found the desired number.
2) After the loop is executed, we return -1. This will work if the searched value is not found during the loop execution. Otherwise, if the searched value is found, its position will be returned in line 8, and after the return command, we will completely exit the search(int) method.[] nums, int target).
3) Inside the loop, we changed the sequence (to recalculate the middle of the array after the low and high boundaries have changed), because we need to calculate the middle of the array after we have cut off some of the elements and recalculated the low/high boundaries.
Let's look at how the low and high boundaries change in a little more detail so that everything becomes clear:
In the case where the value in position mid (the middle of the range) is less than the desired value – we move to the right. That is, we need to discard the left part, and the lower boundary (low) will move to the place where the middle was, +1. We already checked the middle in the first step, when we entered the cycle – and found out that the desired value is greater than the element in position midaccordingly it is necessary to skip midand move the border low into the cell under index 3. That's exactly why we do it low = mid + 1:
A similar situation occurs when the element under index mid (middle of the range) GREATER than the desired value – this means the desired element is less than the element in the middle, and we need to discard the right part including the middle element – to do this we discard all the elements after midincluding himself mid. An operation similar to the previous one takes place – only in reverse, high = mid – 1:
After optimization and simplification, the final version of binary search looks like this:
public class Main {
public static void main(String[] args) {
int result = search(new int[]{1, 3, 5, 6, 9}, 99);
System.out.println(result);
}
public static int search(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (target == nums[mid]) {
return mid;
}
if (target > nums[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}I sincerely hope that I was able to explain things in simple terms. If you have reached this point, you are a great guy!
Continue studying algorithms and stay tuned for new publications!
