【算法】二分搜索的递归实现算法（有重复元素取最小序列）

给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，可以利用二分查找递归实现，达到复杂度为O（log(n))。

但是传统的算法在有重复元素情况如 “1 1 1 1 1 1 ”时，想要找1元素，会返回序号为3.

int BSearch(elemtype a[],elemtype x,int low,int high) 
/*在下届为low，上界为high的数组a中折半查找数据元素x*/ 
{ 
int mid; 
if(low>high) return -1; 
mid=(low+high)/2; 
if(x==a[mid]) return mid; 
if(x<a[mid]) return(BSearch(a,x,low,mid-1)); 
else return(BSearch(a,x,mid+1,high)); 
}

但当遇到有重复元素取最小序列的情况可如下更改：

输入：先输入进行二分搜索元素的个数，然后按大小依次输入（或随机生成，然后排序）每个数字，最后输入要求搜索的元素。

输出：要求搜索元素的下标（下标从0开始！）。

示例：输入：6 1 5 5 9 6 9 6，输出3

//（如果有相同元素取最小的序号）
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+7;
int a[maxn];
int n;

int erfen(int left,int right){
    if(left>right) return -1; 
    if(left==right || a[left] == n)return left;
    else{
        if(n>a[(left+right)/2])return erfen((left+right)/2+1,right);
        if(n<=a[(left+right)/2])return erfen(left,(left+right)/2-1);
    }
}

int main(){
    int m;
    cin>>m;
    for(int i=0;i<m;i++)cin>>a[i];
    cin>>n;
    sort(a,a+m);
    cout<< erfen(0,m-1);
    return 0;
}