TL;DR
――It's a basic point, but in order to keep it in mind, I will write the code for binary search and summarize the explanation in Python. ――I will write the code myself for studying (without using the standard module for binary search). ――Since I was originally a graduate of a school in the design field, please forgive me for any knowledgeable points in the computer science field.
Binary search is one of the algorithms for searching values for a sorted array. Also known as a binary search.
The condition is that the array to be searched is sorted, but it has the property that the search is less likely to slow down even if the target list becomes larger than a normal search.
The method is to first get the value in the center of the list and then compare whether the value in the center is larger or smaller than the value you are searching for.
If the value to be searched is smaller than the center value of the array, this time, the range of the array is narrowed down from the left edge to the range before the center value.
On the other hand, if the value to be searched is larger than the center value, the range of the array is narrowed down from the value one right of the center value to the right end of the array.
After that, the center value is taken in the range of the narrowed array, and it is judged again whether the value to be searched is larger or smaller than the center value, and the array is narrowed down.
If the value to be searched matches the value in the center of the array, it means that the value to be searched has been found, and the search ends there.
Consider the case where you search for the value of 2 in the sorted list[1, 1, 2, 3, 3, 4, 5, 6, 6, 7, 8].
First, get the value in the center of the list. The first median value is 4.
The value 2 to be searched is smaller than the median value 4, so narrow the list to the left of the 4 part and get the value[1, 1, 2, 3, 3]. To.
Get the median value again in the narrowed list. This time the value in the center of the list is 2. Since this does not match the 2 of the search target, the search ends when it is determined that the target exists.
In the normal search process, the search is performed to see if they match in order from the beginning. The calculation order is $ O (n) $ (however, if the value to be searched exists at the beginning, it will be less), and the larger the number of arrays ($ n $), the longer the linear processing time. It will become.
On the other hand, in the case of binary search, the calculation order is $ O (log_2 n) $, so even if the size of the array becomes large, the processing time will be bloated.
While a binary search is faster than a normal search, it can only be used with a sorted array for a binary search (unless it is sorted, the magnitude relationship will be strange when splitting the array. ).
Therefore, in the case where the array to be searched is not sorted and the search is executed only once, the calculation cost of sorting is higher than that of normal search, and the merit of using binary search is There is none.
On the other hand, if the array has already been sorted, or if the search process is repeated many times, the calculation cost can be kept lower by using the binary search even if the sort is executed.
You can use binary search for a list of characters as well as a numerical value, but this time we will proceed as a sample with a list that stores integers.
Also, instead of controlling to return the index of the search result, we will simply check whether the list contains values.
from typing import List
list_value: List[int] = [
100, 23, 33, 51, 70, 32, 34, 13, 3, 79, 8, 12, 16, 134, 83]
sorted_list: List[int] = sorted(list_value)
def binary_search(sorted_list: List[int], search_value: int) -> bool:
"""
Perform a binary search to see if the value to be searched is included in the list
Get the boolean value.
Parameters
----------
sorted_list : list of int
A list containing sorted integer values.
search_value : int
The value to be searched.
Returns
-------
value_exists : bool
Whether the value is included in the list.
"""
left_index: int = 0
right_index: int = len(sorted_list) - 1
while left_index <= right_index:
middle_index: int = (left_index + right_index) // 2
middle_value: int = sorted_list[middle_index]
if search_value < middle_value:
right_index = middle_index - 1
continue
if search_value > middle_value:
left_index = middle_index + 1
continue
return True
return False
I will touch the chords in order.
First of all, in binary search, the target list needs to be sorted, so the sorted function is used to sort the list (the sort method etc. does not change).
list_value: List[int] = [
100, 23, 33, 51, 70, 32, 34, 13, 3, 79, 8, 12, 16, 134, 83]
sorted_list: List[int] = sorted(list_value)
Next is the processing of the binary search function.
left_index: int = 0
right_index: int = len(sorted_list) - 1
Variables for handling the index range of the target list are set as left_index and right_index. The leftmost index of the list is left_index and the rightmost index is right_index. These values are updated on one side each time they are bisected until the loop finishes the search.
while left_index <= right_index:
The process of dividing into two is repeatedly executed in a while loop. This loop repeats as long as the leftmost index is to the left of the rightmost index or has the same intex. If it is to the right of the index at the right end, the range of the target list is exhausted (all targets have been searched), so the loop is terminated and it is judged that the target was not found. ..
middle_index: int = (left_index + right_index) // 2
middle_value: int = sorted_list[middle_index]
Inside the loop, middle_index stores the median value in the target array range. Divide by 2 by // 2 and truncate the fraction (//behaves like a floor in addition to division).
It also refers to that index as well as the center index and sets the center value to a variable (middle_value).
if search_value < middle_value:
right_index = middle_index - 1
continue
In the if statement, if the value to be searched is smaller than the center value, the array is divided into only the left half, so the rightmost index (right_index) is set to the left of the center index (middle_index --1". ).
-1 instead of the central index. if search_value > middle_value:
left_index = middle_index + 1
continue
On the other hand, if the value to be searched is larger than the center value, adjust the value of the leftmost index (left_index) so that the array is only the right half.
return True
If the value to be searched is neither smaller nor larger than the median value, that is, if it is the same as the median value, True is returned as the value to be searched exists.
return False
I will actually run it. First, try from the condition that the target exists in the list.
value_exists = binary_search(
sorted_list=sorted_list,
search_value=83)
print(value_exists)
True
True is returned normally. Next, try specifying the conditions that the search target is not included in the list.
value_exists = binary_search(
sorted_list=sorted_list,
search_value=84)
print(value_exists)
False
This is also False as expected.
Recommended Posts