二分搜索：对排好序的一位数组改进二分搜索(C/C++/Java)

题目:    

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

回顾:

我们先来用C/C++来实现二分法：

(具体步骤讲解都在代码中的注释，所以我就不多讲了)

先用递归法熟悉一下:

#include<iostream>
using namespace std;
int BinarySearch(int arr[],int L,int R,int p)               //arr数组,size数组长度,需要找的p 
{
	if(L>=R)
	{
		while(L <= R)							//大条件就是L要不大于R 
		{
			int mid = L + (R - L)/2;    			//区间中值 
			if(p == arr[mid])					//判断是否符合 
				return mid+1;					//返回 
			else if(p > arr[mid])				//进一步判断p是满足mid的左边还是右边
					return BinarySearch(arr,mid,R,p);	//设置新的查找区间的左端点
			else
					return BinarySearch(arr,R,mid,p);	//设置新的查找区间的右端点 
		}
	}
	else
		return -1;
}

int main()
{
	int arr[100],n,m;
	puts("请设置你要出入的元素个数:");
	cin>>n;
	puts("请输入你要输入的各个元素:");
	for(int i = 0;i < n;i ++)
		cin>>arr[i];
	puts("请输入你要查找的元素:");
	cin>>m;
	puts("对应位置为:");
	cout<<BinarySearch(arr,0,n,m)<<endl;
	return 0;
}

再用for循环来遍历二分查找:

#include<iostream>
using namespace std;
int BinarySearch(int arr[],int size,int p)	                //arr数组,size数组长度,需要找的p 
{
	int L = 0;						//左区间 
	int R = size - 1;					//右区间 
	while(L <= R)						//大条件就是L要不大于R 
	{
		int mid = L + (R - L)/2;			//区间中值 
		if(p == arr[mid])				//判断是否符合 
			return mid+1;				//返回 
		else if(p > arr[mid])				//进一步判断p是满足mid的左边还是右边
				L = mid + 1;			//设置新的查找区间的左端点
		else
				R = mid - 1;			//设置新的查找区间的右端点 
	}
	return -1;						//未找到 
}

int main()
{
	int arr[100],n,m;
	puts("请设置你要出入的元素个数:");
	cin>>n;
	puts("请输入你要输入的各个元素:");
	for(int i = 0;i < n;i ++)
		cin>>arr[i];
	puts("请输入你要查找的元素:");
	cin>>m;
	puts("对应位置为:");
	cout<<BinarySearch(arr,n,m)<<endl;
	return 0;
}

注意事项：

        二分法道理很简单都是平时写的时候，容易忽略区间边界的问题导致运行出错；

        例如int mid = L + (R - L)/2;我们要注意这些细节性问题；

(懂上面写的二分法之后，再来看下面改进过后用Java来实现的二分搜索算法)

示例代码:

import java.util.Scanner;

class Search{
    public static void main(String[] args)
    {
        int[] arr = {1,2,3,4,5,6,7};
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        in.close();
        int mid = BinarySearch(arr,s);
        if(mid >= 0)//判断搜索过后是否返回-1，若是，则结束，若不是，则打印s在数组中的下标位置;
        	System.out.println(s+"所在数组中的下标为:"+mid);
    }
    public static int BinarySearch(int[] arr,int s)
    {
        int L = 0;              //左区间
        int R = arr.length-1;   //右区间
        int mid,i = 0,j = 0;
        while(L  arr[mid])
                    L = mid + 1;
                else
                    R = mid - 1;
        }
        /*当s不在数组中我们可以分成两种情况：1、s大于数组最大值；2、s小于数组最大值；*/
        if(s > arr[arr.length-1])
        	System.out.println("数组中小于"+s+"的最大元素下标:"+i);
        else
        	if(s < arr[arr.length-1])
        		System.out.println("数组中大于"+s+"的最小元素下标:"+j);
        	else
        	{
        		System.out.println("数组中小于"+s+"的最大元素下标:"+i);
        		System.out.println("数组中大于"+s+"的最小元素下标:"+j);
        	}
        return -1;//在数组中未搜索到则返回-1
    }
}

代码仅供参考，看懂思路自己琢磨自己敲，只有在通过练习中领悟和体会其中的抽象，之后遇见什么问题都是迎刃而生的思考；