1.4.18数组的局部最小元素。编写一个程序，给定一个含有N个不同整数的数组，找到一个局部最小元素:满足a[i]<a[i-1],且a[i]<a[i+1]的索引i。程序在最坏情况下所需的比较次数为~2lgN。

答：检查数组的中间值a[N/2]以及和它相邻的元素a[N/2-1]和a[N/2+1]。如果a[N/2]是一个局部最小值则算法终止；否则则在较小的相邻元素的半边中继续查找。

说明：按照上面的提示写出下面的代码不能将这个排列中的局部最小找出来。排列：7  6  9  5  4  3  2  1 中的6找不出来。

public class E1d4d18

{

    public static int min(int[] a)

    {

        int lo=1;

        int hi=a.length-1;

        int mid;

        while(lo<hi)

        {

            mid=(lo+hi)/2;

             if(mid-1>=0 && a[mid-1]<a[mid])

                hi=mid-1;

            else if(mid+1<a.length && a[mid]>a[mid+1])

                lo=mid+1;

            else

                return mid;

        }

        return -1;

    }

   

    public static void main(String[] args)

    {

      int[] a=In.readInts(args[0]);

      StdOut.println(min(a));

    }

}

按照下面版本的代码可以避免上述问题，算法是选从mid-1与mid+1中较小的一边找，找不到时再从mid-1与mid+1中较大的一边找。

public class E1d4d18

{

    public static int min(int[] a)

    {

        int lo=1;

        int hi=a.length-2;

        int mid;

        int localMinIndex=-1;

        //find in rang smaller

      while(lo<=hi && localMinIndex==-1)

        {

            mid=(lo+hi)/2;

            if(a[mid]<a[mid-1] && a[mid]<a[mid+1])

                localMinIndex=mid;

            else if(a[mid-1]<a[mid+1])

                hi=mid-1;

            else if(a[mid-1]>a[mid+1])

                lo=mid+1;

        }

       //

      lo=1;

      hi=a.length-2;

      while(lo<=hi && localMinIndex==-1)

      {

          mid=(lo+hi)/2;

          if(a[mid]<a[mid-1] && a[mid]<a[mid+1])

              localMinIndex=mid;

          else if(a[mid-1]<a[mid+1])

              lo=mid+1;

          else if(a[mid-1]>a[mid+1])

              hi=mid-1;

      }

      return localMinIndex;

    }//end min

    public static void main(String[] args)

    {

      int[] a=In.readInts(args[0]);

      StdOut.println(min(a));

    }

}