剑指offer—第二章算法之二分查找(旋转数组的最小值)

旋转数组的最小数字

题目：把一个数组最开始的若干元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如：数组{3,4,5,1,2}为{1，2,3,4,5}的一个旋转数组。此时的旋转数组是可以划分为两个排序的子数组。最小值为这两个子数组分界线。

思路：写一个函数minArrary（int*arrary int len）,返回值为int。定义三个指针left=mid=0（如果数组是将前面的0个元素放到数组的后面，那么旋转数组即是原数组，最小值即为mid（left）处的值）,right,并且初始化。分别指向数组的头，中，尾部。如果数组的长度小于等于0或者arrary为空，则抛异常为空。如果当满足array[left]>array[right]时，如果right-left==1,mid=right;break;mid=(right+left);如果array[left]==arrary[right],arrary[left]==array[mid],只能顺序查找。int min=array[left],当满足计数变量i<right 时候，比较array[i]与min的值，将较小的值赋值给min,这个时候的时间复杂度为O（n）。如果arrary[mid]>arrary[left],则有left=mid；如果有arrary[mid]<arrary[right],则有right=mid；返回mid处的值。

#include<iostream>

#include<stdio.h>

#include<string>

using namespace std;

int array[1000001];

//求旋转数组最小值

int MInArray(int *array,int n){

	int left = 0;

	int right = n - 1;

	int mid = 0;

	//二分查找最小值

	while(array[left] >= array[right]){

		//如果相邻right下标为最小值

		if(right - left == 1){

			mid = right;

			break;

		}

		mid = (left + right) / 2;

		//如果下标为left,right,mid的数值相等，只能顺序查找

		if(array[left] == array[right] && array[left] == array[mid]){

			int min = array[left];

			//顺序查找最小值

			for(int i = left + 1;i <= right;i++){

				if(min > array[i]){

					min = array[i];

				}

			}

			return min;

		}

		//mid 处于第一递增排序序列 最小值在mid后面

		if(array[mid] >= array[left]){

			left = mid;

		}

		//mid 处于第二递增排序序列 最小值在mid前面

		else if(array[mid] <= array[right]){

			right = mid;

		}

	}

	return array[mid];

}

int main()

{

	int i,n;

	while(scanf("%d",&n) != EOF){

		for(i = 0;i < n;i++){

			scanf("%d",&array[i]);

		}

		printf("%d\n",MInArray(array,n));

	}

    return 0;

}

java代码：

public class RotatingArray {

     public int rotateArray(int a[]){

         int left=0;

         int mid=0;

         int right=a.length-1;

         while(a[left]>=a[right]){

             if((right-left)==1){

                 mid=right;

                 break;

            }

             mid=(left+right)/2;

             if(a[left]==a[mid]&&a[mid]==a[right]){

                 //只能用顺序查找最小值

                 int min=a[left];

                 for(int i=left;i<=right;i++){

                     if(a[i]<min)

                         min=a[i];

                 }

                return min;

             }

             if(a[mid]>=a[left])

                 left=mid;

             else if(a[mid]<=a[left])

                 right=mid;

         }

         return a[mid];

     }

     public static void main(String[] args){

         int[] a={4,5,6,1,2,3};

         RotatingArray ra=new RotatingArray();

         int min=ra.rotateArray(a);

         System.out.println(min+" ");

     }

}

巴特西

剑指offer—第二章算法之二分查找(旋转数组的最小值)

最新文章

热门文章