要明白二分查找是個(gè)什么思想.個(gè)人比較熟悉,不寫二分思想說明.
一定要注意:使用二分之前,一定要排好序,要不然怎么進(jìn)行二分查找呢. 具體看代碼:(這里是用for循環(huán)實(shí)現(xiàn)的,后面的代碼是用遞歸實(shí)現(xiàn).)
package com.qf.demo2;
public class Test3 {
public static void main(String[] args) {
int[] a= {1,4,7,9,10,13,18,19};
int index = binarySearch(a, 111);
System.out.println(index);
}
public static int binarySearch(int[] a,int b){
int minIndex = 0;
int maxIndex = a.length-1;
for(int i = 0; i<a.length/2+1;i++){
int middleIndex = (minIndex+maxIndex)/2;
if(a[middleIndex] == b){
return middleIndex;
}else if(a[middleIndex]>b){// 左邊的情況 , 需要改變的是最大的下標(biāo)
maxIndex = middleIndex-1;
}else if(a[middleIndex]<b){// 右邊的情況, 需要改變的是最小的下標(biāo)
minIndex = middleIndex+1;
}
}
return -1;
}
}
package com.qf.demo2;
import java.util.Arrays;
public class Ef {
public static void main(String[] args) {
int[] a = {9,8,1,4,2,6};
//先排序
Arrays.sort(a);
int index = ef(a,2,0,5);
System.out.println(index);
}
static int ef(int[] a,int key,int max,int min){
int mid = (min+max)/2;
if(a[mid] == key){
return mid;
}else if(a[mid] > key){
return ef(a, key, min, mid-1);
}else{
return ef(a, key, mid+1, max);
}
}
}
