题目描述

/已知折半查找的部分代码如下，勿改动。请补充实现折半查找算法Bin_Search。
要求：实现方式为递归方法。
/

include
using namespace std;

const int MaxSize=100; //顺序表的最大长度
//有序表类
class LinearSearch{
public:
LinearSearch(){n=0;}
~LinearSearch(){}
void Insert(int x);//有序表的插入，使序列仍有序
void DispList(); //输出表
int Bin_Search(int key); //调用下面的递归算法
int Bin_Search(int low, int high, int key); //递归算法，成功返回位置，否则返回0
private:
int r[MaxSize+1]; //存储元素(r[1]~r[n]存储元素)
int n; //顺序表实际长度
};

//在有序表中插入元素x，使序列仍有序
void LinearSearch::Insert(int x){
int i;
if (n>=MaxSize) //表满不能插入
throw “Overflow”;
r[0]=x;
for(i=n;r[i]>x;i—)
r[i+1]=r[i];//将i位置元素后移
r[i+1]=x; //在位置i+1插入元素x
n++; //线性表长度增1
}
void LinearSearch::DispList() //输出表
{
int i;
cout<<”Data:”;
for(i=1;i<=n;i++)
{
cout< }
cout<}
//在下面补充实现折半查找算法（两个函数Bin_Search，1个形参和3个形参的各一个）
int main(){
LinearSearch A; //空表A
int x,key;
//利用插入函数创建有序表，以0结束
while(1){
cin>>x;
if(!x)break;
try{
A.Insert(x);
}
catch(char *wrong){
cout< }
}
A.DispList();
int pos;
cin>>key;
pos=A.Bin_Search(key);
if(!pos)//查找失败
cout<<”Find “< else cout<<”Find “< return 0;
}

输入

输入数据以0结束

输出

注意测试查找成功及失败两种情况

样例输入

43 53 1 25 2 426 324 345 423 34 0 43

样例输出

Data:1 2 25 34 43 53 324 345 423 426
Find 43 success,position:5

提示

来源

提交

import java.util.Scanner;
class LinearSearch{
    int n = 0;
    int[] r;
    int MaxSize = 100;
    public LinearSearch() {
        r = new int[MaxSize];
    }
    void insert(int x) throws Exception {
        int i;
        if (n>MaxSize)         //表满不能插入
            throw new Exception("Overflow");
        r[0]=x;
        for(i=n;r[i]>x;i--)
            r[i+1]=r[i];//将i位置元素后移
        r[i+1]=x;//在位置i+1插入元素x
        n++;//线性表长度增1
    }
    void DispList(){
        System.out.print("Data:");
        for (int i = 1; i <= n; i++) {
            System.out.print(r[i]+" ");
        }
        System.out.println();
    }
    int Bin_Search(int key){
        return Bin_Search(1,n,key);
    }
    int Bin_Search(int low,int high,int key){
        if(low>high)
            return -1;
        int mid = (low + high) >> 1;
        if(r[mid] > key)
            return Bin_Search(low, mid - 1, key);
        else if(r[mid] < key)
            return Bin_Search(mid + 1, high, key);
        return mid;
    }
}
public class Main {
    public static void main(String[] args) throws Exception {
        LinearSearch linearSearch = new LinearSearch();
        Scanner scanner = new Scanner(System.in);
        int key;
        while(true){
            int x = scanner.nextInt();
            if(x == 0)break;
            linearSearch.insert(x);
        }
        key = scanner.nextInt();
        linearSearch.DispList();
        int pos = linearSearch.Bin_Search(key);
        if(pos!=-1){
            System.out.println("Find "+key+" success,position:"+pos);
        }else{
            System.out.println("Find "+key+" failure");
        }
    }
}