上课笔记(5)(1)——＃593. 二分查找(binary)

Description

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

Format

Input

第一行：一个整数，表示由小到大序列元素个数；

下面 n 行，每行一个整数；

最后一行一个整数 x，表示待查找的元素；

Output

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

Samples

输入数据 1

5
3
5
6
6
7
6

输出数据 1

3

Limitation

1s, 1024KiB for each test case.

方法一：

 看这名字就知道要用二分，但我不信邪，试了试暴力搜，竟然AC了！，不得不吐槽一下，那个OJ的数据是真的水。

程序：

#include<bits/stdc++.h>//不建议使用本程序，很有可能爆零 
using namespace std;
int n,x,a[1000010];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    	cin>>a[i];
    cin>>x;
    for(int i=1;i<=n;i++)
    	if(a[i]==x){
    		cout<<i;
    		return 0;
    	}
    coutt<<-1;
    return 0;
}

方法二：

就是正常的二分查找，大致思路就是开两个变量设定范围然后根据变的之间值不断缩小范围纸质找到，注意在数组是有序的情况下才能进行二分，要么就先排序。

程序：

#include<bits/stdc++.h>
using namespace std;
int n,x,a[1000010];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    	cin>>a[i];
    cin>>x;
    int l=1,r=n; 
	while(l<=r){
    	int mid=(l+r)/2;
    	if(a[mid]<x)
			l=mid+1;
    	else 
			r=mid-1;
	}
	if(a[l]!=x){
		cout<<-1;
		return 0;
	}
	cout<<l;
    return 0;
}

PS:方法一请谨慎使用！