实验一 分治与递归—二分搜索 java实现

 提高题一:二分搜索

一、实验目的与要求

1、熟悉二分搜索算法;

2、初步掌握分治算法;

二、实验题

1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时,Ij相同,均为x在数组中的位置。

2、设有n个不同的整数排好序后存放于t[0:n-1]中,若存在一个下标I0in,使得t[i]=i,设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为Ologn)。

三、实验提示

1、用Ij做参数,且采用传递引用或指针的形式带回值。

boolBinarySearch(int a[],intn,intx,int&i,int& j)

{

    int left=0;

    int right=n-1;

    while(left<right)

    {

       int mid=(left+right)/2;

        if(x==a[mid])

       {

           i=j=mid;

           return true;

       }

        if(x>a[mid])

           left=mid+1;

       else

           right=mid-1;

    }

    i=right;

    j=left;

    return false;

}

 

intSearchTag(int a[],intn,int x)

{

    int left=0;

    int right=n-1;

    while(left<right)

    {

       int mid=(left+right)/2;

        if(x==a[mid]) return mid;

        if(x>a[mid])

           right=mid-1;

       else

           left=mid+1;

    }

    return -1;

}

四、源代码

//递归法

importjava.util.*;

import java.io.*;

 

 

public class SF_SearchRecursively

{

       public static void main(String[] args)

       {

              Scanner read=new Scanner(System.in);

              System.out.println("请输入一个数组的大小:");

              int n=read.nextInt();

              System.out.println("请输入一个数组的元素:");

              int a[]=new int [n];

              for (inti=0;i<n ;i++ )

              {

                     a[i]=read.nextInt();

              }

              System.out.println("您输入的数组为:");

              for (inti=0;i<n ;i++ )

              {

                     System.out.print(a[i]+"\t");

              }

              System.out.println();

              System.out.println("*******进行数组的二分搜索:*******");

              System.out.println("*******排序后:********");

              Arrays.sort(a);

              for (inti=0;i<n ;i++ )

              {

                     System.out.print(a[i]+"\t");

              }

              System.out.println();

              System.out.println("请输入一个要查找的元素:");

              int x=read.nextInt();

              int w=searchRecursively(a,x,n);

              if (w!=(-1))

              {

                     System.out.println("您查找的元素:"+x+"在第数组的"+w+"");

              }else{System.out.println("没有该元素在数组中");}

       }

 

       public static intsearchRecursively(int[]data,intkey,intlen) {

              if (data==null||len<1)return -1;

              returndoSearchRecursively(data,0,len-1,key);

              }

 

 

       private static intdoSearchRecursively(int[] data, int low, inthigh,int key) {

              if (low > high)

                     return -1;

              int mid = (low + high) / 2;

              if (key < data[mid]) {

                     returndoSearchRecursively(data, low, mid - 1, key);}

                     else if (key > data[mid]) {

                            returndoSearchRecursively(data, mid + 1, high, key);}

                            else {

                                   return mid;}

       }

}

 

//分治法

importjava.util.*;

import java.io.*;

 

public class test{

 

public static int find(int[] data,intgoal,intleft,int right){

int mid = (left+right)/2 ;  

if(left>right){   

return -1 ;    

        }       

if(goal==data[mid]){  

return mid ;

        } 

else if(goal<data[mid]){

            //注意right = mid -1 ;

return find(data,goal,left,mid-1);

        }

else if(goal>data[mid]){       

return find(data,goal,mid+1,right);

        } 

return -1 ;        

    }      

 

public static void main(String[] args){

              Scanner read=new Scanner(System.in);

              System.out.println("请输入一个数组的大小:");

              int n=read.nextInt();

              System.out.println("请输入一个数组的元素:");

              int a[]=new int [n];

              for (inti=0;i<n ;i++ )

              {

                     a[i]=read.nextInt();

              }

              System.out.println("您输入的数组为:");

              for (inti=0;i<n ;i++ )

              {

                     System.out.print(a[i]+"\t");

              }

              System.out.println();

              System.out.println("*******进行数组的二分搜索:*******");

              System.out.println("*******排序后:********");

              Arrays.sort(a);

              for (inti=0;i<n ;i++ )

              {

                     System.out.print(a[i]+"\t");

              }

              System.out.println();

              System.out.println("请输入一个要查找的元素:");

              int x=read.nextInt();

              int result =find(a,x,0,n) ;

              if (result!=(-1))

              {

                     System.out.println("您查找的元素:"+x+"在第数组的"+result+"");

              }else{System.out.println("没有该元素在数组中");}

 

    }

 

}

结果:

 

实验一 分治与递归—二分搜索 java实现

 

实验一 分治与递归—二分搜索 java实现



本文转自 梦朝思夕 51CTO博客,原文链接:http://blog.51cto.com/qiangmzsx/818746

上一篇:3分钟了解阿里云容器服务


下一篇:macvlan 网络结构分析 - 每天5分钟玩转 Docker 容器技术(56)