hiho一下 第三十六周 二分·二分查找

http://hihocoder.com/contest/hiho36/problem/1

题意：

给你一个无序的数组，问一个元素是第几位小

思路：

可以直接暴力找一下，但是也是可以借此练一下二分

按照这个思路，选出一个Mid，然后二分，这个Mid的选择可以参照快排的写法

int Partition(int l, int r) {
    int i = l, j = r;
    Point pivot = a[l];
    while(i < j) {
        while(i < j && a[j].value > pivot.value) j --;
        if(i < j) swap(a[i ++], a[j]);
        while(i < j && a[i].value <= pivot.value) i ++;
        if(i < j) swap(a[i], a[j --]);
    }
    return i;
}

AC代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 5;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define LL long long

struct Point{
    LL value;
    int id;
};

Point a[maxn];
int n;
LL m;

int Partition(int l, int r) {
    int i = l, j = r;
    Point pivot = a[l];
    while(i < j) {
        while(i < j && a[j].value > pivot.value) j --;
        if(i < j) swap(a[i ++], a[j]);
        while(i < j && a[i].value <= pivot.value) i ++;
        if(i < j) swap(a[i], a[j --]);
    }
    return i;
}

int Binary(int l, int r, LL value) {
    while(l <= r) {
        int mid = Partition(l, r);
        if(a[mid].value == value) return mid;
        else if(a[mid].value > value) return Binary(l, mid - 1, value);
        else return Binary(mid + 1, r, value);
    }
    return -1;
}

int main()
{
   scanf("%d %lld", &n, &m);
   for (int i = 1; i <= n; i ++) {
        scanf("%lld", &a[i].value);
        a[i].id = i;
    }
   printf("%d\n", Binary(1, n, m));
    return 0;
}