hihocoder第三十六周 二分查找

　　题目链接：http://hihocoder.com/contest/hiho36/problem/1 , 一个比较简单的二分。

---

算法：

　　由于数据量比较大，O(nlogn)无法通过，所以不能先排序再查找。由于题目中问的是在排序后的位置，所以可以想到快速排序中一趟排序后，作为支点的那个值的坐标就已经确定下来了，所以可以把要查找的k作为支点，这样的话一趟排序后(即把比k小的放在k之前，比k大的放在k之后)，k的坐标即为所求。

　　至于给的提示表示没看懂。。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <vector>

#include <string>

#include <string.h>

#include <algorithm>

using namespace std;

const int maxn =  + ;

int a[maxn];

int main()

{

    int n , k , i , j , pos;

    scanf("%d %d" , &n , &k);

    for(i =  ; i <= n ; i++) {

        scanf("%d" , &a[i]);

    }

    for(pos =  ; pos <= n ; pos++)

        if(a[pos] == k)

            break;

    if(pos > n) {

        printf("-1\n");

    } else {

        i = ;

        j = n;

        while(i != j) {

            while(a[j] > k && j > pos)

                j--;

            a[pos] = a[j];

            pos = j;

            while(a[i] < k && i < pos)

                i++;

            a[pos] = a[i];

            pos = i;

        }

        printf("%d\n" , i);

    }

    return ;

}