C++二分查找递归算法，二分法查询重复值

原理：在一个已经排好序的数组中查询关键词所在的地方

第一步：首先确定整个查找区间的中间位置 mid = strat+(end-strat)/2

第二步：用待查关键字key值与中间位置的关键字值进行比较；

若相等，则查找成功

若大于，则在后（右）半个区域继续进行折半查找

若小于，则在前（左）半个区域继续进行折半查找

第三步：反复递归

原理引用大佬的解释咯，他的原文有非递归的代码讲解！
 

代码：

#include<bits/stdc++.h>

using namespace std;

//二分查找
 int TwoSearch(int key,int arr[],int start,int ends){
        if(start >ends){
            return -1;
        }
        int mid=start+(ends-start)/2;   //也可以用移位：start+((ends-start)>>1),防溢出，更高效
        if(key<arr[mid]){
            return TwoSearch(key,arr,start,mid-1);
        }
        else if(key>arr[mid]){
            return TwoSearch(key,arr,mid+1,ends);
        }
        else if(key == arr[mid]){
            return mid;
        }
}

int main(){
    int key;
    int arr[]={0,1,2,4,5,7,7,9};    //8个数字的顺序数组
    cin>>key;
    cout<<key<<"所在的位置是：第"<<TwoSearch(key,arr,0,sizeof(arr)/sizeof(int)-1)+1<<"项"<<endl;
    return 0;
}

测试查询第一个数字：

测试查询最后一个数字：

 测试查询有重复的数字：

 发现从左遍历查询到第一个7的位置，就结束了。

若我将mid=start+(ends-start)/2；改为mid=start+((ends-start)/2+1);也就是出现偶数个时，我从右边遍历，发现，会显示右边7的位置，

 寻思着，那我，判断一下，如果这个数字出现了两遍或以上，我就从左遍历一下，右边也遍历一下，是不是就好了，代码：

#include<bits/stdc++.h>

using namespace std;

//二分查找
 int TwoSearch_left(int key,int arr[],int start,int ends){
        if(start >ends){
            return -1;
        }
        int mid=start+(ends-start)/2;   //从左遍历
        if(key<arr[mid]){
            return TwoSearch_left(key,arr,start,mid-1);
        }
        else if(key>arr[mid]){
            return TwoSearch_left(key,arr,mid+1,ends);
        }
        else if(key == arr[mid]){
            return mid;
        }
}

 int TwoSearch_right(int key,int arr[],int start,int ends){
        if(start >ends){
            return -1;
        }
        int mid=start+((ends-start)/2+1);   //从右遍历
        if(key<arr[mid]){
            return TwoSearch_right(key,arr,start,mid-1);
        }
        else if(key>arr[mid]){
            return TwoSearch_right(key,arr,mid+1,ends);
        }
        else if(key == arr[mid]){
            return mid;
        }
}

int main(){
    int key;
    int sum=0;
    int arr[]={0,1,2,4,5,7,7,9};    //8个数字的顺序数组
    cin>>key;
    for(int i=0;i<8;i++){
        if(key == arr[i])
            sum++;
    }
    if(sum == 1)
        cout<<key<<"所在的位置是：第"<<TwoSearch_left(key,arr,0,sizeof(arr)/sizeof(int)-1)+1<<"项"<<endl;
    else if(sum >= 2){
        cout<<key<<"所在的位置是：第"<<TwoSearch_left(key,arr,0,sizeof(arr)/sizeof(int)-1)+1<<"项"<<endl;
        cout<<key<<"所在的位置是：第"<<TwoSearch_right(key,arr,0,sizeof(arr)/sizeof(int)-1)+1<<"项"<<endl;
    }
    return 0;
}

测试其他值没变化，测试7时发生了变化：

那，新问题来了，要是7出现了3次呢，我修改了下数组，

 结果：

 。。。。。。很难受，就只能查出两项，一下子莫得思路了，，以后有思路了或遇到大佬了，，再来想这个问题吧。。。