Class notes (5) (1) - 593. Binary search

Description

Give a yes n  A sequence of elements from small to large , Please program to find the position where an element first appears .(n≤10^6)

Format

Input

first line ： An integer , Indicates the number of sequential elements from small to large ;

below  n That's ok , One integer per row ;

The last line is an integer  x, Represents the element to be found ;

Output

If  x In the sequence , The output  x  First occurrence , Otherwise output -1.

Samples

input data 1

5
3
5
6
6
7
6

Output data 1

3

Limitation

1s, 1024KiB for each test case.

Method 1 ：

  Look at this name, you know it needs two points , But I don't believe in evil , Tried the violent search , actually AC 了 ！, I have to make complaints about it , that OJ The data is real water .

Program ：

#include<bits/stdc++.h>// This procedure is not recommended , It is likely to explode  
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;
}

Method 2 ：

Is the normal binary search , The general idea is to open the setting range of two variables, and then reduce the range according to the value between the variables, and find it on paper , Note that only when the array is ordered can it be bisected , Or sort it first .

Program ：

#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: Method 1 please use it carefully ！