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;
}
