lupohsunrock的部落格

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package binarySearch;

/**
 *
 * @author lupohsun
 */

import javax.swing.JOptionPane; //引進JOptionPane視窗化輸出入介面類別
import java.util.Random; //引進隨機數產生類別
import java.util.Arrays; //引進陣列類別，排序用

public class Main {

    private int count = 0; //宣告來計算時間複雜度
    public void setCount(int c) {
        this.count = c;
    }
    public int getCount() {
        return this.count;
    }

    //binarysearch方法
    public int binarysearch(int l,int h,int x,int[] a) {
        if(l > h)                
            return 0;
        else {
            int mid = (l+h)/2;
            if(a[mid] == x) {
                count();
                return mid+1;
            }
            else if(a[mid]                 count();
                return binarysearch(mid+1,h,x,a);
            }
            else {
                count();
                return binarysearch(l,mid-1,x,a);
            }
        }
    }

    //計算時間複雜度方法，由binarysearch()呼叫
    public void count() {
        int c = getCount();
        c = c+1;
        setCount(c);
    }
   
    public static void main(String[] args) {       

        //輸入變數數量以及key值
        String s;
        s = JOptionPane.showInputDialog("請輸入變數的數量");
        int n;
        n = Integer.parseInt(s); /* 變數的數量為n */
        s = JOptionPane.showInputDialog("請輸入key值\n請注意變數的值為0到99");
        int x;
        x = Integer.parseInt(s);
        s = "變數的數量為：" +n +"\nkey值為：" +x;
        JOptionPane.showMessageDialog(null,s);  /* 顯示已輸入的變數數量以及key值 */

        /*以下為亂數產生，產生值的範圍為0~99*/
        Random random = new Random();   /* random是一個static method，不能直接呼叫 */
        int[] array = new int[n];   /*宣告一個大小為n的陣列*/
        for(int i=0;i                 array[i] = random.nextInt(100);    /*在陣列中產生n個變數*/
                System.out.println("array[" +i +"]:" +array[i]);   /*印出陣列中的所有變數*/
        }

        /*排序*/
        System.out.println("排序後：");
        Arrays.sort(array);
        for(int i=0;i               System.out.println("array[" +i +"]:" +array[i]); //印出排序後的陣列
        }

        /*binarysearch*/       
        int h = n-1;
        int l = 0;
        int result = 0;
        Main main = new Main(); //binarysearch()是一個static method，不能直接參照
        result = main.binarysearch(l,h,x,array); //呼叫binarysearch()
        if(result != 0) {
            result -= 1;
            s = "key值的位置在 array[" +result +"]\n比較次數為" +main.getCount();
        }
        else
            s = "所有變數中找不到此key值\n比較次數為" +main.getCount();
        JOptionPane.showMessageDialog(null,s); //顯示key值的位置
    }
}