二分法查找数组

　　如果想要通过二分法查找数组中的某一个特定的值，该数组一定是有序数组，即如果一个无序数组想要利用二分法查找数组中的某一个特定的值，需要先将数组排序，然后再用二分法进行查找。二分法进行查找数组主要有两种方式，第一种是利用地递归实现二分查找，另一种是利用非递归即循环的方式实现二分查找。具体的代码实现如下：

　　递归方法：

#include <iostream>
#include <cstring>
#include <fstream>
#include <cstdio>
#include <algorithm>

using namespace std;


int searchBinary(int s,int a[], int low, int high){
    if(low > high){
        return -1;
    }else {
        int mid = (low + high)/2;
        if(s == a[mid]){
            return mid;
        }else if (s < a[mid]){
            return searchBinary(s,a,low,mid-1);
        }else {
            return searchBinary(s,a,mid + 1,high);
        }
    }

}


int main()
{
    int arr[] = {0,1,2,3,4,5,6,7,8,9,10};
    int index = searchBinary(2,arr,0,10);
    cout << index << endl;

}

　　非递归方法：

#include <iostream>
#include <cstring>
#include <fstream>
#include <cstdio>
#include <algorithm>

using namespace std;


/*int searchBinary(int s,int a[], int low, int high){
    if(low > high){
        return -1;
    }else {
        int mid = (low + high)/2;
        if(s == a[mid]){
            return mid;
        }else if (s < a[mid]){
            return searchBinary(s,a,low,mid-1);
        }else {
            return searchBinary(s,a,mid + 1,high);
        }
    }

}


int main()
{
    int arr[] = {0,1,2,3,4,5,6,7,8,9,10};
    int index = searchBinary(2,arr,0,10);
    cout << index << endl;

}*/
int BinSearch(int a[], int n, int key){
    int low = 0;
    int high = n - 1;
    int mid;
     while (low <= high){
        mid = (low + high)/2;
        if(key == a[mid]){
            return mid;
        }else if ( key < a[mid]){
            high = mid - 1;
        } else{
            low = mid + 1;
        }
     }
     return -1;
}

int main(){
    int arr[] = {0,1,2,3,4,5,6,7,8,9,10};
    int index = BinSearch(arr,11,2);
    cout << index << endl;
}

二分法查找数组

相关推荐