二分查找的四种简单实现

//二分查找判断某个元素是否在序列里
long search(int a[],int low,int high,int k){
    if(low <= high){
        int mid = low + (high - low) / 2;
        if(k == a[mid]){
            return 1;//找到了返回1
        }else if(a[mid] > k){
//比中值小在左边找            
            return search(a, low, mid - 1, k);
        }else{
//比中值大在右边找            
            return search(a, mid + 1, high, k);
        }
    }
    return 0;
//如果都找不到默认返回0    
}

//oj的题目是给定长度为n的不下降序列，做m个询问
//1.从左逼近(直接丢函数包)
long fun(long a[],long low,long high,long key)
{
    int mid = low + (low + high) / 2;
    if(low <= high){
        if(a[mid] < key){
//在右边查找            
            return fun(a, mid + 1, high, key);
        }
        if(a[mid] > key){
//在左边查找            
            return fun(a, low, mid - 1, key);
        }
        else{
/*如果找到目标元素，判断有无重复，有的话取最大下标*/
            while(mid>=0){
                if(a[mid]!=key){
                    break;
                }
                mid++;
            }
        }
    }
    return mid;
}

//二分查找(从右逼近)
long fun(int a[],int target ,int temp)
{
    int low = 0, high = target, int temp, mid;
    while(low < high){
        mid = (low + high) / 2;
        if(a[mid] == taret){
            high = mid;
        }
        else if(a[mid] > target){
            high = mid;
        }else{
            low = mid + 1;
        }
    }
    if(a[temp] < target){
        return temp + 2;
    }
    /*这里是来区分有没有找到目标值，只要从始至终都没有找到目标
    元素，返回n+2*/
    return low + 1;
}

/*计算包含再给定区间里的序列数值的个数*/
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
//这里输入的序列是不按照顺序的
int left(int a[], int target, int temp) {
	int low = 0, high = temp;
	int mid;
//左端不断向右边逼近    
	while (low < high) {
		mid = (low + high) / 2;
		if (a[mid] == target) {
			low = mid + 1;
		}else if (a[mid] < target) {
			low = mid + 1;
		}
		else if (a[mid] > target) {
			high = mid;
		}
	}
	return low;
}
int right(int a[], int target, int temp) {
	int low = 0, high = temp;
	int mid;
//右端不断向左端逼近    
	while (low < high) {
		mid = (low + high) / 2;
		if (a[mid] == target) {
			high = mid;
		}
		else if (a[mid] > target) {
			high = mid;
		}
		else if (a[mid] < target) {
			low = mid + 1;
		}
	}
	return low;
}

int main()
{
	int i, j, k, n, m, p, q;
	cin >> n >> m;
//n表示有几个数字，m表示要输入几组数字
	int* a = (int*)malloc(n * sizeof(int));
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	for (j = 0; j < m; j++) {
		cin >> p >> q;//p<=q，p是左区间，q是右区间
		cout << left(a, q, n) - right(a, p, n) << endl;
/*left把n不断往左靠，使得右边界逼近q，right把p不断右移，
不断逼近右边界*/
	}
	free(a);
}
/*排完序后再放进函数里，left的作用:
对比左数和序列里的每一个数,返回小于p的数的序号
right是让q与序列的数比较，返回大于q的序号
然后大减小就得到了区间里包含的数*/