求教一个二分查找的程序

Question

求教一个二分查找的程序

Answer 1

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

Answer 2

我这个菜鸟来帮他翻印吧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));         
     } 
  }

Answer 3

Arrays.binarySearch(int[]a, value)
java中已经有比较优化的方法实现了，直接调用即可

Answer 4

Arrays, Collections中分别有关于数组和Collection的查找方法供调用.

Answer 5

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