二分查找

左手的ㄟ右手 2021-09-21 17:12 269阅读 0赞

> ### 一、自己实现的 ###

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    
    using namespace std;
    
    int arr[100];
    
    //二分查找 
    bool BinarySearch(int n, int target){
    	int left = 0;
    	int right = n-1;
    	while(left <= right){
    		int middle = left + (right - left) / 2;
    		if(arr[middle] < target){
    			left = middle+1;
    		}else if(arr[middle] > target){
    			right = middle - 1;
    		}else{
    			return true;
    		}
    	}
    	return false;
    }
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	for(int i = 0; i < n; ++i){
    		scanf("%d",&arr[i]);
    	}
    	//二分查找必须是有序序列，所以在查找之前要排序 
    	sort(arr,arr+n);
    	int m;
    	scanf("%d",&m);
    	for(int i = 0;i < m; ++i){
    		int target;
    		scanf("%d",&target);
    		if(BinarySearch(n,target)){
    			printf("YES\n");
    		}else{
    			printf("NO\n");
    		}
    	}
    	return 0;
    }

> ### 二、系统自带的 ###

c++内置二分查找

\#include < algorithm >

**一、binary\_search：查找某个元素是否出现。**  
函数模板：  
binary\_search(arr\[\], arr\[\]+size, target)  
参数说明：  
arr\[\]： 数组首地址  
size：数组元素个数  
target:需要查找的值  
函数功能： 在数组中以二分法检索的方式查找，若在数组(要求数组元素非递减)中查找到indx元素则真，若查找不到则返回值为假。  
**二、lower\_bound：查找第一个大于或等于某个元素的位置。**  
函数模板：  
lower\_bound(arr\[\],arr\[\]+size ,target)  
参数说明：  
arr\[\]： 数组首地址  
size：数组元素个数  
target:需要查找的值  
函数功能： 函数lower\_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置(注意是地址)。如果所有元素都小于val，则返回last的位置

**注意：**函数lower\_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！值为n.  
返回查找元素的第一个可安插位置，也就是“元素值>=查找值”的第一个元素的位置

**三、upper\_bound：查找第一个大于某个元素的位置。**

函数模板：

upper\_bound(arr\[\],arr\[\]+size , target)

参数说明：

arr\[\]： 数组首地址

size：数组元素个数

target:需要查找的值

函数功能：函数upper\_bound()返回的在前闭后开区间查找的关键字的上界，返回大于val的第一个元素位置

例如：一个数组number序列1,2,2,4.upper\_bound(2)后，返回的位置是3（下标）也就是4所在的位置,同样，如果插入元素大于数组中全部元素，返回的是last。(注意：数组下标越界)

返回查找元素的最后一个可安插位置，也就是==“元素值>查找值”==的第一个元素的位置 。

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    
    using namespace std;
    
    int arr[100];
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	for(int i = 0; i < n; ++i){
    		scanf("%d",&arr[i]);
    	}
    	//二分查找必须是有序序列，所以在查找之前要排序 
    	sort(arr,arr+n);
    	int m;
    	scanf("%d",&m);
    	for(int i = 0;i < m; ++i){
    		int target;
    		scanf("%d",&target);
    		//lower_bound获取的是地址值 
    		int position = lower_bound(arr,arr + n,target)-arr;
    		if(position != n && arr[position == target]){
    			printf("YES\n");
    		}else{
    			printf("NO\n");
    		}
    	}
    	return 0;
    }