Shulou(Shulou.com)06/02 Report--

This article mainly explains how to use Android binary search algorithm. Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let Xiaobian take you to learn "how to use Android binary search algorithm"!

Minimum number of rotation array

Moving the first elements of an array to the end of the array is called rotation of the array.

Input a rotation of an incrementally-sorted array and output the smallest element of the rotated array. For example, array {3, 4, 5, 1, 2} is a rotation of {1, 2, 3, 4, 5}, and the minimum value of this array is 1.

To rotate an array, see Left Rotation String.

problem-solving ideas

As with binary search, two pointers are used to point to the first and last elements of the array.

Notice that the rotated array can actually be divided into two sorted subarrays, and that the elements of the preceding subarray are greater than or equal to the elements of the following subarray.

We can also notice that the smallest element happens to be the dividing line between these two subarrays. We try to find this smallest element using binary search thinking.

First we use two pointers to the first and last element of the array. According to the rules of rotation, the first element should be greater than or equal to the last element (this is not exactly true, there are exceptions. Special cases discussed later).

Then we have to go around the middle of the array. If the middle element is in the preceding incrementing subarray, it should be greater than or equal to the element pointed to by the first pointer.

The smallest element in the array should be located after the middle element. We can narrow down the search by pointing the first pointer to the middle element.

Similarly, if the middle element is in the next incrementing subarray, it should be less than or equal to the element pointed to by the second pointer.

The smallest element in the array should precede the middle element. We can also narrow the search by pointing a second pointer to the middle element. We then use the updated two pointers to get and compare the new intermediate elements and loop on.

Following the above line of thought, our first pointer always points to the element of the preceding incrementing array, and our second pointer always points to the element of the following incrementing array.

The last pointer will point to the last element of the preceding subarray, while the second pointer will point to the first element of the following subarray. That is, they end up pointing to two adjacent elements, and the second pointer just happens to point to the smallest element. This is the condition for the cycle to end.

Core implementation code:

Note: When two pointers point to the same number and their middle number, we cannot tell whether the middle number is located in the previous word array or the subsequent subarray, and we cannot move the two pointers to narrow the search range. At this point, we have to adopt a sequential search method.

2 Find a number in a rotation array

Requirement: A rotation array without duplicate elements (its corresponding original array is ordered), find the index of the given element in the rotation array (no return-1).

for example

The ordered array is {0, 1, 2, 4, 5, 6, 7}, and one of its rotation arrays is {4, 5, 6, 7, 0, 1, 2}.

Element 6 in rotation array, returns 2

Element 3 is not in the rotation array, returns-1

analysis

Time complexity is O(n), because it is an ordered array rotation, which is definitely not an optimal solution. order n. instinctive n. reflection n. binary n. search n. give an example of a trait

It can be seen that at least one of the two segments in the middle position is ordered (either left or right), so you can use binary search in the ordered range; if it is no longer in the ordered range, go to the other half to find it.

reference code

extended

The existence of edges is to have no duplicate elements. Now, with a slight extension, there can be duplicate elements, and other requirements remain unchanged.

The idea: roughly the same idea as the original, this is to compare the relationship between A[beg] and A[mid]

Number of times a number appears in a sorted array

At this point, I believe that everyone has a deeper understanding of "how to use Android binary search algorithm," so let's actually operate it! Here is the website, more related content can enter the relevant channels for inquiry, pay attention to us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.