# offer rotation array

Moving the first elements of an array to the end of an array is called array rotation. Input a rotation of a non decreasing sort array and output the smallest element of the rotated array. For example, if the array {3,4,5,1,2} is a rotation of {1,2,3,4,5}, the minimum value of the array is 1. NOTE: all elements given are greater than 0. If the array size is 0, please return 0.

Idea: it can be seen that the rotation array is composed of two parts of increasing sequence, and its minimum value is the edge of the two parts, that is, the number smaller than the previous incremental sequence.

1. A slight improvement of sequential search

```# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
left = 0
right = len(rotateArray)-1
if not len(rotateArray):
return 0

minn = rotateArray
for i in range(1,len(rotateArray)):
if minn > rotateArray[i]: #Encountered the first number of the following increasing sequence
minn = rotateArray[i]
break
return minn```

2. The application of binary search

```  class Solution:
def minNumberInRotateArray(self, rotateArray):
#This question mainly tests the application of binary search
left = 0
right = len(rotateArray) - 1
if not len(rotateArray):
return 0
#Guaranteed to be a rotated array
while (rotateArray[left] >= rotateArray[right]):
# If the left pointer is adjacent to the right pointer, the decimal is the number that the right pointer refers to
if ((right - left) == 1):
mid = right
break
mid = (right + left) / 2
#If the middle number of the array is the same as the left pointer and the right pointer, for example: [1,0,1,1,1]
#Then search in order
if (rotateArray[mid] == rotateArray[left] and rotateArray[right]):
return min(rotateArray)
#If the number of left pointer is less than the number of intermediate elements of the array, it is proved that the number of intermediate elements of the array is in the previous incremental array. At this time, the left pointer points to the intermediate element
#On the contrary, the number of intermediate elements is in the following incremental array, and the right pointer is used to point to the number of intermediate elements
#At this point, we can see that the left element always points to the front incremental array, and the right element always points to the subsequent incremental array. When the left and right pointers are adjacent, the number of right pointers is the minimum
if (rotateArray[left] < rotateArray[mid]):
left = mid
else:
right = mid
return rotateArray[mid]```

Keywords: less

Added by h3ktlk on Thu, 09 Jul 2020 18:59:09 +0300