7. Rotate the minimum number of the array

subject

Moving the first few elements of an array to the end of the array is called the rotation of the array. Enter a rotation of a non-subtractive 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 the array is 1. NOTE: All the elements given are greater than 0. If the array size is 0, please return 0.

Basic idea

It is definitely impossible to traverse directly, thus losing the significance of this problem.

The rotating array is actually formed by splicing two ordered arrays, so we can use dichotomy and only need to find the splicing point.

(1)array[mid] > array[high]:

The array in this case is similar to [3,4,5,6,0,1,2], and the minimum number must be to the right of mid.
low = mid + 1

(2)array[mid] == array[high]:

Array with this situation are similar to [1,0,1,1,1] or [1,1,1,0,1], and the minimum number is not easy to judge to the left of mid at this time
Or on the right, then had to try one by one.
high = high – 1

(3)array[mid] < array[high]:

Arrays with this situation are similar to [2,2,3,4,5,6,6], and the minimum number must be array[mid] or to the left of mid.
Edge. Because the right must be increasing.
high = mid

Code

function minNumberInRotateArray(arr)
 {
 let len = arr.length;
 if(len == 0)  return 0;
 let low = 0, high = len - 1;
 while(low < high) {
 let mid = low + Math.floor((high-low)/2);
 if(arr[mid] > arr[high]) {
 low = mid + 1;
 } else if(arr[mid] == arr[high]) {
 high = high - 1;
 } else {
 high = mid;
 }
 }
 
 return arr[low];
 }

extend

binary search

function binarySearch(data, arr, start, end) {
 if (start > end) {
 return -1;
 }
 var mid = Math.floor((end + start) / 2);
 if (data == arr[mid]) {
 return mid;
 } else if (data < arr[mid]) {
 return binarySearch(data, arr, start, mid - 1);
 } else {
 return binarySearch(data, arr, mid + 1, end);
 }
 }