What are the Binary Search Limitations

Binary search idea

Look for a number between 0 and 99. Whenever we look for a number, we take the middle number to judge. When the middle number is large, it's like an interval from 0 to middle. When it's small, it's like a mid-99 interval. When we're looking for 23

The binary search is directed to an ordered set. Each time it is compared to the middle element of the interval, the interval to search is reduced by half until the element is found, or the interval is reduced to 0

Complexity of the binary search time O (logn)

Assuming that the search interval is n, it ends every time it is reduced by half, in the worst case only when it is reduced to 0.

If n / 2kWhen = 1, K is the total number of reductions. Each reduction includes a comparison of the elements. After k is reduced, the time complexity is O (k) to n / 2k= 1, then k = log (n), so the time complexity is O (logn) which is an extremely efficient time complexity

Simple implementation of binary search

Binary Search Limitations

1 binary search dependent array
Is it possible to use a linked list? The answer is no. Binary search mainly uses random access to data based on the complexity of the index O (1)

2 The binary search is based on the data that has been ordered

3 The amount of data is too small to be suitable for binary search
If it's too small, just go through it one by one

4 The amount of data is too large to be suitable for binary search
Since I have a binary search dependent array and therefore need continuous storage, this is unrealistic when 1G of data requires 1G of continuous storage

Variant of binary search

The binary search implemented above does not take into account the fact that the array contains duplicate data. Let's analyze this situation below.

Variation one Find the first dates that correspond to this element


There are double elements. We want to find the first value equal to 8, which corresponds to the value of index 5, but not that the index is 6 and 7

Take a look at the implementation

If the value and the data you are looking for are the same and the data is already the first or last data of mid that is not equal to that value, go straight back, otherwise it means that there is duplicate data in front of you and set high = mid -1, keep looking

Variant 2 Find the last element that corresponds to the value

The idea is the same as above

Variant three Find the first element that is greater than or equal to the specified value

Variant 4 Find the last element that is less than or equal to the specified value