10051 二分查找

题目描述

给出有 n 个元素的由小到大的序列，请你编程找出某元素第一次出现的位置。(n<=10^6)

第一行：一个整数，表示由小到大序列元素个数；下面 n 行，每行一个整数；最后一行 一个整数 x，表示待查找的元素；

如果 x 在序列中，则输出 x 第一次出现的位置，否则输出-1。

输入 #1

5
3
5
6
6
7
6

3

[二分]

C++题解代码

#include <bits/stdc++.h>
using namespace std;

int a;
int c;
int d;
int e;
int b[1000001];


// 描述该功能...
int fn(int x, int y, int z) {
  if (y >= x) {
    e = (x+((y-x)/2));
    if (b[e] == z) {
      return e;
    } else if (b[e] > z) {
      return fn(x, (e-1), z);
    } else {
      return fn((e+1), y, z);
    }
  } else {
    return (-1);
  }
}

// The main procedure
int main() {
  cin>>a;
  for (int i = 1; i <= a; i++) {
    cin>>b[i];
  }
  cin>>c;
  d = fn(1, a, c);
  while ((d > 1) && (b[(d-1)] == b[d])) {
    d--;
  }
  cout<<d;
  return 0;
}

Blockly题解代码图片