我们再继续学习之前,先了解一个简单的二分查找法
利用数组,来查找内部是否含有一个数字,并返回数字的下标
| public static int BinarySearch_test1(int[] a, int key) {
//这次的目的是为了进行二分法 int Fir = 0; int Las = a.length – 1; //之所以减一是因为索引为数量-1 while(Fir<=Las) { int mid = (Fir + Las)/2; //从中间进行判断 if (key > a[mid]) { Fir = mid+1; }else if (key < a[mid]) { Las = mid-1; }else { return mid; } } return -1; } |
上面要求数组是有序的
方可以使用二分查找法,上面中,我们每次从区间的中间进行判断,
不断的缩小区间,最后找到我们所查找的数字的对应下标
在之后,可以看一下二分法和排序算法的结合
public static Comparable select(Comparable []a ,int k){
int lo = 0,int hi = a.length-1;
while(hi>lo){
int j = partition(a,lo,hi);
if(j == k){return a[k];
else if(j>k){hi=j-1;}
else if(j>k){lo=j+1;}
return a[k];
}
}
partition则是利用快速排序的方式获取到的