提高题一：二分搜索
一、实验目的与要求
1、熟悉二分搜索算法；
2、初步掌握分治算法；
二、实验题
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）。
三、实验提示
1、用I，j做参数，且采用传递引用或指针的形式带回值。
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("没有该元素在数组中");}
}
}
结果：
本文转自 梦朝思夕 51CTO博客，原文链接:http://blog.51cto.com/qiangmzsx/818746
