二分查找

1.非顺序表查找最大值递归算法

   private static int divideSearchMax(int[] a, int left, int right){
        if(left==right){
            return a[left];
        }else if((left+1)==right){
            return a[left] > a[right] ? a[left] : a[right];
        }else{
            int mid=(left+right)/2;
            int max1=divideSearchMax(a, left, mid);
            int max2=divideSearchMax(a, mid+1, right);
            return max1 > max2 ? max1: max2;
        }
    }

2.顺序表的二分查找算法
查找下标最小的特定元素x

• 递归实现

   public static int binarySearch(int[] a, int x, int left, int right){
        if(left <= right){
            int mid=(left + right)/2;
            if(a[mid]==x){
                int t = mid;
                while(a[t]==x && t>=0)
                    t--;
                return t+1;
            }
            else if(a[mid]>x)
                return binarySearch(a, x, left, mid-1);
            else 
                return binarySearch(a, x, mid+1, right);
        }
        return -1;
    }

• 非递归实现

   public static int binarySearch(int[] a, int x){
        int l=0, r=a.length-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(a[mid]==x){
                int t = mid;
                while(a[t]==x && t>=0)
                    t--;
                return t+1;
            }
            if(x > a[mid])
                l=mid+1;
            else r=mid-1;
        }
        return -1;
    }