求教一个二分查找的程序
求教一个二分查找的程序
[解决办法]
public class arrayBinary{
public static int bsearch(int array[],int value){
boolean found=false;
int high=array.length-1;
int low=0;
int cnt=0;//查找步数
int mid=(high+low)/2;
System.out.println("Looking for "+value);
while(!found&&(high>=low)){
System.out.print(" Low "+low+" Mid "+mid);
System.out.print(" High "+high);
if(value==array[mid])
found=true;
else
if(value< array[mid])
high=mid-1;
else
low=mid+1;
mid=(high+low)/2;
cnt++;
}
System.out.println();
System.out.println("Steps "+cnt);
return((found)?mid:-1);
}
public static void main(String[] args){
int array[]=new int[100];
for(int i=0;i< array.length;i++)
array[i]=i;
System.out.println("Resulte "+bsearch(array,67));
System.out.println("Resulte "+bsearch(array,33));
System.out.println("Resulte "+bsearch(array,1));
System.out.println("Resulte "+bsearch(array,1001));
}
}
[解决办法]
看看数据结构就知道了
[解决办法]
我这个菜鸟来帮他翻印吧
public class arrayBinary{ /** * @param 要查找的数组和要查找的值，前提是数组要从小到大排列好 */ public static int bsearch(int array[],int value){ boolean found = false; // 是否找到 int high = array.length - 1; // 二分法中的要查找的高位 int low = 0; // 二分法中的要查找的低位 int cnt = 0; //查找步数 int mid = (high + low)/2; // 二分法要点，二分啊 System.out.println("Looking for "+value); while(!found && (high >= low)){ // 边界条件 System.out.print(" Low " + low + " Mid " + mid); System.out.print(" High " + high); if(value == array[mid]) // 等于中间的值，找到了 ;) found = true; else // 没找到 ;( if(value < array[mid]) // 若要找的数比中间的数小，当然到数组的前半部分找 high = mid - 1; // 将高位变成中间那个数的前一个数 else // 若要找的数比中间的数还大，当然到数组的后半部分找喽 low = mid + 1; // 将低位变成中间那个数还大一个数 mid = (high + low)/2; // 不管是前部分还是后部分，找到中间的那个位置先 cnt++; // 又查了一步了哦 } System.out.println(); System.out.println("Steps " + cnt); return((found) ? mid : -1); // 找到还是没找到啊，没找到，-1给你吧 } public static void main(String[] args){ int array[]=new int[100]; for(int i=0;i < array.length;i++) array[i]=i; System.out.println("Resulte "+bsearch(array,67)); System.out.println("Resulte "+bsearch(array,33)); System.out.println("Resulte "+bsearch(array,1)); System.out.println("Resulte "+bsearch(array,1001)); } }
[解决办法]
顶
[解决办法]
Arrays.binarySearch(int[]a, value)
java中已经有比较优化的方法实现了，直接调用即可
[解决办法]
Arrays, Collections中分别有关于数组和Collection的查找方法供调用.
[解决办法]
public class Sorter {
private int[] array;
private int temp = 0;
// 对数组排序
public void sortArray(int[] array) {
this.array = array;
// 应插入的位置
int locate = 0;
for (int i = 1; i < array.length; i++) {
temp = array[i];
// 二分法查找应插入的位置
locate = findLocation(0, i - 1);
if (locate != i) {
// 插入到有序数组中
insertIntoLocation(i, locate);
}
}
}
// 第归的二分查找法,返回应插入的位置
private int findLocation(int header, int tail) {
int mid = (header + tail) / 2;
// 找到相同的结果，返回
if (temp == array[mid]) {
return mid + 1;
}else if (mid == tail) { // 查找到有序数组的最后一个位置
if (temp > array[mid]){
return mid + 1;
} else {
return mid;
}
} else {
if (temp < array[mid]) { // 在左半部分查找
return findLocation(header, mid - 1);
} else { // 在右半部分查找
return findLocation(mid + 1, tail);
}
}
}
// 将temp值插入有序数组
private void insertIntoLocation(int originalIndex, int changeIndex) {
for (int i = originalIndex; i > changeIndex; i--) {
array[i] = array[i - 1];
}
array[changeIndex] = temp;
}
public static void main(String[] args) {
Sorter sorter = new Sorter();
int[] array = new int[]{8,6,7,3,5,4,8,10, 112, 12, 8, 7, 145, 132};
sorter.sortArray(array);
for(int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}
以前写的用二分查找排序的类；
核心就是这一块
// 要查找的值temp和有序数组array为简单起见声明为类变量了。
// 第归的二分查找法,返回应插入的位置
private int findLocation(int header, int tail) {
int mid = (header + tail) / 2;
// 找到相同的结果，返回
if (temp == array[mid]) {
return mid + 1;
}else if (mid == tail) { // 查找到有序数组的最后一个位置
if (temp > array[mid]){
return mid + 1;
} else {
return mid;
}
} else {
if (temp < array[mid]) { // 在左半部分查找
return findLocation(header, mid - 1);
} else { // 在右半部分查找
return findLocation(mid + 1, tail);
}
}
}