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

 <b>提高题一：二分搜索</b>

<b>一、实验目的与要求</b>

1、熟悉二分搜索算法；

2、初步掌握分治算法；

<b>二、实验题</b>

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

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

<b>三、实验提示</b>

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

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

{

    int left=0;

    int right=n-1;

    while(left&lt;right)

    {

       int mid=(left+right)/2;

        if(x==a[mid])

       {

           i=j=mid;

           return true;

       }

        if(x&gt;a[mid])

           left=mid+1;

       else

           right=mid-1;

    }

    i=right;

    j=left;

    return false;

}

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

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

    return -1;

<b>四、源代码</b>

<b></b>

<b>//</b><b>递归法</b>

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&lt;n ;i++ )

              {

                     a[i]=read.nextInt();

              }

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

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

              System.out.println();

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

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

              Arrays.sort(a);

              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&lt;1)return -1;

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

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

              if (low &gt; high)

                     return -1;

              int mid = (low + high) / 2;

              if (key &lt; data[mid]) {

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

                     else if (key &gt; data[mid]) {

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

                            else {

                                   return mid;}

<b>//</b><b>分治法</b>

public class test{

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

int mid = (left+right)/2 ;  

if(left&gt;right){   

return -1 ;    

        }       

if(goal==data[mid]){  

return mid ;

        } 

else if(goal&lt;data[mid]){

            //注意right = mid -1 ;

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

        }

else if(goal&gt;data[mid]){       

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

return -1 ;        

    }      

public static void main(String[] args){

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

              if (result!=(-1))

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

结果：

<a href="http://blog.51cto.com/attachment/201203/193205562.png" target="_blank"></a>

<a href="http://blog.51cto.com/attachment/201203/193221989.png" target="_blank"></a>

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