二分查找法的问题

Question

public class Tester
{
    private final static int capacity = 100;
    private static double[] ary = new double[capacity];    public static void main(String[] args)
    {
        generateArray();
        sortArray();
        double num = randomNumber();
        int position = searchArray(num, 0, capacity);
        showResult(position, num);
    }    private final static int max = 1000;
    private static double randomNumber()
    {
        return Math.random() * 1000;
    }    private static void generateArray()
    {
        for (int i = 0; i < capacity; i++)
            ary[i] = randomNumber();
    }    private static void sortArray()
    { // Simple Sort Algorithm
        for (int i = 0; i < capacity - 1; i++)
            for (int n = i + 1; n < capacity; n++)
                if (ary[i] > ary[n])
                {
                    double temp = ary[i];
                    ary[i] = ary[n];
                    ary[n] = temp;
                }
    }    private static int searchArray(double num, int left, int right)
    { // Binary Search Algorithm
        if (right <= left)
            return left;        int point = (right - left) / 2 + left;
        if (ary[point] == num)
            return point;        if (ary[point] < num)
            return searchArray(num, point + 1, right);
        else
            return searchArray(num, left, point - 1);
    }    private static void showResult(int pos, double num)
    {
        System.out.println("Searched number: " + num);
        double num1 = ary[pos];
        if (num1 == num)
        {
            System.out.println(num1);
            return;
        }        if (num1 < num)
        {
            System.out.println(ary[pos]);
            if (++pos < capacity)
                System.out.println(ary[pos]);
        }
        if (num1 > num)
        {
            if (--pos >= 0)
                System.out.println(ary[pos]);
            System.out.println(ary[pos+1]);
        }
    }
}

Answer 1

将下面的有关int的改为double就可以了：
/**  BiSearch.java
* create an array of 100 integers, sort it, binary search for a given value;
*/
import java.io.*;
import java.util.Random;
public class BiSearch 
{
public static void swap(int[] data, int i, int j){
int t = data[i];
data[i] = data[j];
data[j] = t;
}
public static int find(int[] data, int x){
int low = 0, high = data.length-1;
int mid;
while(low<=high){
mid = (low + high)/2;
if(data[mid]==x) return mid;
else if(data[mid]>x) high = mid-1;
else low = mid+1;
}
return -1;
} public static void dump(int[] data){
System.out.println("数组内容:");
for(int i=0; i<data.length; i++){
System.out.print(data[i] + ", ");
}
System.out.println("");
}
public static void selectionSort(int[] data, int n){
int unSorted = n;
int index;
int max;
while(unSorted > 0){
max = 0;
for(index = 0; index< unSorted; index++){
if(data[max] < data[index]) max = index;
}
swap(data, max, unSorted-1);
unSorted --;
}
} public static void main(String[] args) 
{
final int SIZE = 100;
int [] arr= new int[SIZE];
Random r = new Random(0);
 
for(int i=0; i<SIZE; i++){
arr[i] = r.nextInt()%1000;
}
dump(arr);
selectionSort(arr, SIZE);
dump(arr);
String s;
try{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   System.out.println("请输入查找的数(按回车结束):");
while((s=in.readLine()).length()!=0){
int x = Integer.parseInt(s);
int pos;
pos = find(arr, x);
if(pos>=0){
System.out.println("位置:" + pos + ", 数值:" + arr[pos]);
if(pos>0)
System.out.println("前一个值:" + arr[pos-1]);
if(pos<arr.length-1)
System.out.println("下一个值:" + arr[pos+1]);
}
else
System.out.println("没有找到:" + x);
System.out.println("请输入查找的数(按回车结束):");
}
}catch(Exception e){
System.out.println(e);
System.exit(0);
}
}
}

Answer 2

hayai(生命树)和onestab(一刺)的方法比较我比较喜欢onestab的方法
因为效率比较好，hayai的方法使用递归的方法效率要差很多。
感谢你们的帮助，以下是我的程序，希望大家取长补短，共同进步。import java.io.*;
import java.util.*;
class nuts1_6{
  public static void main(String[] args)throws IOException{
    double[] d=new double[100];
    d=CreateDoubleArray.create(100);
    Arrays.sort(d);
    for(int i=0;i<d.length;i++){
      System.out.print(d[i]+"  ");
      if(i%4==0)
        System.out.println();
      }
    
      BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    for(;;){
      int i=0;
      System.out.print(">");
      String line=in.readLine();
      if((line==null)||(line.equals("quit"))) break;
      try{
      double j=Double.parseDouble(line);
      i=CreateDoubleArray.FindDouble(d,j);
      }
      catch(NumberFormatException e){
        System.out.println("please input a double");
        continue;
      }
      if(i==-1)
        System.out.println("Can't find");
      else 
        System.out.println(i);
    }
     }
}
    
  
  

Answer 3

以下是一个更通用的二分法查找的源程序：import java.util.*;
class CreateDoubleArray{
  static double[] create(int n){
    double[] d=new double[n];
    for(int i=0;i<n;i++)
      d[i]=Math.random()*100;
    return d;
  }
  static int FindDouble(double[] d,double j){
    int left=0;
    int right=d.length-1;
    if(j==d[left])
      return left;
    if(j==d[right])
      return right;
    for(;;){
      if(j==d[(left+right)/2]){
        return (left+right)/2;
      }
      else if(j<d[(left+right)/2])
        right=(left+right)/2;
      else if(j>d[(left+right)/2])
        left=(left+right)/2;
      if(left==(left+right)/2)
        return -1;
    }
  }
}
import java.io.*;
import java.util.*;
class nuts1_6{
  public static void main(String[] args)throws IOException{
    double[] d=new double[100];
    d=CreateDoubleArray.create(100);
    Arrays.sort(d);
    for(int i=0;i<d.length;i++){
      System.out.print(d[i]+"  ");
      if(i%4==0)
        System.out.println();
      }
    
      BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    for(;;){
      int i=0;
      System.out.print(">");
      String line=in.readLine();
      if((line==null)||(line.equals("quit"))) break;
      try{
      double j=Double.parseDouble(line);
      i=CreateDoubleArray.FindDouble(d,j);
      }
      catch(NumberFormatException e){
        System.out.println("please input a double");
        continue;
      }
      if(i==-1)
        System.out.println("Can't find");
      else 
        System.out.println(i);
    }
     }
}
    

Answer 4

hayai(生命树)和onestab(一刺)的方法比较我比较喜欢onestab的方法
因为效率比较好，hayai的方法使用递归的方法效率要差很多。
感谢你们的帮助，以下是我的程序，希望大家取长补短，共同进步。
import java.io.*;
class nuts1_5{
  
  public static void main(String[] args)throws IOException{
    double[] nums=new double[100];
    for(int i=0;i<nums.length;i++)
      nums[i]=Math.random()*100;
    Arrays.sort(nums);
    for(int i=0;i<nums.length;i++){
      System.out.print(nums[i]+"  ");
      if(i%4==0)
        System.out.println();
      }
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    for(;;){
      System.out.print(">");
      String line=in.readLine();
      if((line==null)||(line.equals("quit"))) break;
      double j=Double.parseDouble(line);
      int left=0,right;
      right=nums.length-1;
      if(j==nums[0]){
        System.out.println(nums[0]);
        continue;
        }
      if(j==nums[right]){
        System.out.println(nums[right]); 
        continue;
        }
      for(;;){
        if(j==nums[(left+right)/2]){
          System.out.println(nums[(left+right)/2]);
          break;
          }
        else if(j<nums[(left+right)/2])
          right=(left+right)/2;
        else if(j>nums[(left+right)/2])
          left=(left+right)/2;
        if(left==(left+right)/2){
          System.out.println(nums[left]+" "+nums[right]);
          break;
          }
     
      }
    }  
  }
}