package datastruct.find;

public class BinarySearch {
	//方法一：非递归折半查找：
	private static void binarySearch(int a[],int k) {
		int low=0;
		int high=a.length-1;
		int mid;
		while (low<=high) {  
			mid=(low+high)/2;
			if (k==a[mid]) {
				System.out.println(a[mid]+"在"+mid+"位置");
			     return;
			}else {
				if (k<a[mid]) {
					high=mid-1;
				}
				else {
					low=mid+1;
				}
			}
		}
		System.out.println("无法查找到该元素！");
	}
	//方法二：使用递归的折半查找
	private static int binarySearch(int a[],int k,int low,int high ) {
		if (a.length<=0) {
			System.out.println("数组内元素为空！");
			return -1;
		} 
		if (low>high) {
			System.out.println("无法查找到该元素！");
			return -1;
		}else {
			int mid=(low+high)/2;
			if (k==a[mid]) {
				System.out.println(a[mid]+"在"+mid+"位置");
			     return mid;
			}else {
				if (k<a[mid]) {
				 return	binarySearch(a, k, low, mid-1);
				}else {
				 return binarySearch(a, k, mid+1, high);
				}
			}
     	}
	}
	
	
     public static void main(String[] args) {
		int a[]={1,2,3,4,5,6,7};
		System.out.println("非递归算法：");
		binarySearch(a, 1);
		binarySearch(a, 2);
		binarySearch(a, 3);
		binarySearch(a, 4);
		binarySearch(a, 5);
		binarySearch(a, 6);
		binarySearch(a, 7);
		System.out.println("递归算法：");
		binarySearch(a, 1, 0, a.length-1);
		binarySearch(a, 2, 0, a.length-1);
		binarySearch(a, 3, 0, a.length-1);
		binarySearch(a, 4, 0, a.length-1);
		binarySearch(a, 5, 0, a.length-1);
		binarySearch(a, 6, 0, a.length-1);
		binarySearch(a, 7, 0, a.length-1);
	}
}


运行结果：

                 非递归算法：

                 1在0位置

                 2在1位置

                 3在2位置

                 4在3位置

                 5在4位置

                 6在5位置

                 7在6位置

                 递归算法：

                 1在0位置

                 2在1位置

                 3在2位置

                 4在3位置

                 5在4位置

                 6在5位置

                 7在6位置

题目：写出折半查找的递归算法。初始调用时，low为1，high为ST.Length
关键字： 折半查找，递归算法
思路：

根据查找的起始位置和终止位置，将查找序列一分为二，判断所查找的关键字在哪一部分，然后用新的序列的起始位置和终止位置递归求解。

首先，确定所需变量

查找表ST，查找目标key，查找起始位置low 和查找终止位置high

（因为本题使用递归算法，说明查找的起始位置和终止位置一直在递归变化，所以需要设为变量）
其次，设计递归出口

即查找结束的情况：

1.查找失败的条件：low>high

2.查找成功的条件：ST.mid==key
分析： 算法把规模为n的复杂问题经过多次递归调用转化为规模减半的子问题求解。

时间复杂度为O（log2  n,）

算法中用到了一个递归工作栈，其规模与递归深度有关，也是O（log2   n）
代码：
typedef struct{
    ElemType *elem;
    int length;
}SSTable;
int BinSearchRec(SSTable ST,ElemType key,int low,int high){//在有序表中递归折半查找其关键字为key的元素，返回其在表中序号
    if (low>high)//查找失败，key不在查找表中
       return 0;
    mid=(low+high)/2;//取中间位置
    if(key>ST.elem[mid])//向后半部分查找
       BinSearchRec(ST,key,mid+1;high);
    else if(key<ST.elem[mid])//向前半部分查找
       BinSearchRec(ST,key,low,mid-1);
    else //查找成功
        return mid;   
}

package Ceshi;

public class biSearch {

	/**
	 * @param args
	 */
	/*
	折半查找--当查找表是有序表时，可采用折半查找;
	基本思想：在有序表中，取中间元素作为比较对象，若给定值K与中间记录关键字相等，则查找成功；
	若给定值K小于中间记录的关键字，则在表的左半区继续查找；
	若给定值K大于中间记录的关键字，则在表的右半区继续查找，不断重复，直到查找成功/失败。
	*/

	//折半查找非递归算法
	//查询成功返回该对象的下标序号，失败时返回-1。
	int BiSearch(int r[],int n,int k)
	{
		int low=0;
		int high=n-1;
		while(low<=high)
		{
			int mid=(low+high)/2;
			if(r[mid]==k)
				return mid;
			else
				if(r[mid]<k)
					low=mid+1;
				else
					high=mid-1;
		}
		return -1;
	}


	//折半查找递归算法
	//查询成功返回该对象的下标序号，失败时返回-1。
	int BiSearch2(int r[],int low,int high,int k)
	{
		if(low>high)
			return -1;
		else
		{
			int mid=(low+high)/2;
			if(r[mid]==k)
				return mid;
			else
				if(r[mid]<k)
					return BiSearch2(r,mid+1,high,k);
				else
					return BiSearch2(r,low,mid-1,k);

		}
	}
	
	public static void main(String[] args) {
		biSearch bs=new biSearch();
		int r[]={1,2,3,4,5};
		System.out.println(bs.BiSearch(r,5,5));
		System.out.println(bs.BiSearch2(r,1,5,5));
	}

}

 
文献来源：
UNDONER(小杰博客) 
：http://blog.csdn.net/undoner
LSOFT.CN(琅软中国) 
：http://www.lsoft.cn


 

设计一个算法，实现折半查找，很简单的问题。在这里列举下递归和非递归
递归实现
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <stack>
#include <algorithm>
#include <queue>

using namespace std;
int n,a[105];

int Search_Bin(int stat,int end,int tmp)
{
	int i,j;
	
	if(stat>end)
		return -1;
	if(stat==end)
	{
		return stat;
	}
	
	if(tmp==a[(stat+end)/2])
	{
		return (stat+end)/2;
	}
	if(tmp>a[(stat+end)/2])
	{
		return Search_Bin((stat+end)/2+1,end,tmp);
	}
	else if (tmp<a[(stat+end)/2])
	{
		return Search_Bin(stat,(stat+end)/2-1,tmp);
	}
}

int main()
{
	int i,j,tmp;
	
	printf("请输入你要随机产生的数的个数\n");	
	scanf("%d",&n);
	srand(time(0));
	for(i=0;i<n;i++)
	{
		a[i]=rand()%1000;
	}
	sort(a,a+n);
	printf("随机产生的数排序后的answer是\n");
	for(i=0;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
	printf("请输入你要查找的数\n");
	scanf("%d",&tmp);
	printf("该数所在的位置是%d个\n",Search_Bin(0,n-1,tmp)+1);
	
	return 0;
}


非递归实现
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <stack>
#include <algorithm>
#include <queue>

using namespace std;
int n,a[105];

int Search_Bin(int stat,int end,int tmp)
{
	int i,j;
	
	printf("该数所在的位置是");
	while(stat<=end)
	{
		if(stat==end)
		{
			printf("%d\n",stat+1);
			break;
		}
		
		if(tmp==a[(stat+end)/2])
		{
			printf("%d\n",stat+1);
			break;
		}
		if(tmp>a[(stat+end)/2])
			stat=(stat+end)/2+1;
		else if(tmp<a[(stat+end)/2])
			end=(stat+end)/2-1;
	}
	
}

int main()
{
	int i,j,tmp;
	
	printf("请输入你要随机产生的数的个数\n");	
	scanf("%d",&n);
	srand(time(0));
	for(i=0;i<n;i++)
	{
		a[i]=rand()%1000;
	}
	sort(a,a+n);
	printf("随机产生的数排序后的answer是\n");
	for(i=0;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
	printf("请输入你要查找的数\n");
	scanf("%d",&tmp);
	Search_Bin(0,n-1,tmp)+1;
	//printf("该数所在的位置是%d个\n",Search_Bin(0,n-1,tmp)+1);
	
	return 0;
}