一、问题描述

在一维数组(非有序状态)中找出一个元素pivot，使得其左边的元素均小于等于它，右边的元素均大于等于它，要求线性时间复杂度的算法.

二、算法分析

首先从左往右扫描整个数组，求出非递减序列，可以用布尔数组标记。

然后在从右往左扫描，记录扫描过程中的最小值rightMin，在非递减序列序列中找到小于等于这个rightMin的元素即可。

举例：

int[] ary = {1,0,1,0,1,2,1,3,1,2};

从左往右扫描，对应的非递减布尔标记数组为：

flag = {true,false,true,false,true,true,false,true,false,false}

对应的非递减序列为：

{ary[0],ary[2],ary[4],ary[5],ary[7]}

也即

{1,1,1,2,3}

从右向左扫描

当扫描到j=6时，ary[j]=1<=rightMin=1，但是ary[j]不在非递减序列中，该元素非中轴元素。

当扫描到j=4时，ary[j]=1<=rightMin=1，同时ary[j]在非递减序列中，中轴元素找到。

其核心思想在于：目标元素大于其前序列的最大值，小于其后序列的最小值。

三、算法实现

/*     * 并不是给定的任何数组都存在这样的中轴元素，例如数组{1,0,3,2}就不存在这样的中轴元素     * 如果存在，则返回该元素的下标。     * 如果不存在，则返回-1     * */    public static int getBoundary(int[] ary,int low,int high){        int leftMax = ary[low],rightMin = ary[high];        boolean[] flag = new boolean[high-low+1];//布尔数组标记从左往右的非递减元素，为true的下标对应到ary中均为非递减序列        for (int i = low; i <= high; i++) {            if (ary[i] >= leftMax) {
   //非递减                leftMax = ary[i];                flag[i] = true;            }else {                flag[i] = false;            }        }        for(boolean value:flag){            System.out.print(value+",");        }        for (int j = high; j >= low; j--) {
   //从右向左扫描            if (ary[j] <= rightMin) {                rightMin = ary[j];                if (flag[j]) {
   return j;}//在非递减序列中找到最后一个小于等于rightMin的元素。            }        }        return -1;//不存在中轴元素    }