Variant of binary search in Java

This example shares the variants of binary search in Java for your reference. The specific contents are as follows

General binary search:

Let's review the common binary search

Note: there is a problem with binary search: when there are duplicates in the array, such as {3,3,3,3}, when binary search for 3, it returns arr [1], that is, binary search will not return the position 0 where 3 appears for the first time.

Dichotomous variant: findfirst function

In the ordinary binary search, search in the [left.... right] left closed right closed interval. If an element with value is found, it is considered to be found. This is not the case in this findfirst function. Search in the [left.... right] left closed right closed interval. When an element with a value equal to value is found, let right = mid instead of right = mid - 1, and continue to search in the [left.... right] left closed right closed interval. Exit the loop when the final left = = right.

After exiting the loop, the value value may be found, or the loop may exit the loop without finding value after traversing the entire array.

So after exiting the loop, you have to judge what kind of situation it is.

Dichotomous variant: fewer function

introduce

Given an array and a variable value, find the number whose value is closest to and smaller than value from the array. For example, arr = {11, 22, 22, 33, 33, 44, 54} value = 33. 22 is closest to value and smaller than value.

So the answer is 2 (22 subscript in array ARR).

If no number smaller than value is found, output - 1.

Solution ideas

Use the binary search method. Use arr [mid] to compare with value every time. Small, equal to, go to the left; Big, go to the right. Maybe you don't quite understand the situation of "equal" in the previous sentence. Ordinary binary search is to find arr [mid] = = value, while fewer function is to find a number smaller than value. Therefore, although arr [mid] = = value, you have to continue to find a smaller value on the left.

example

code

Dichotomous variant: greater function

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.