二分法经典例题

迷南。 2022-02-26 02:44 229阅读 0赞

**三个例题语句大致相同，但是注意判断语句中的符号有差异，请读者慢慢体会.**

**(一)(二)(三)二分全部使用的是左闭右闭区间**

**（一）运用范围：查找是否存在n元素**

#include <stdio.h>
    int main(){
    	int arr[5]={1,5,3,2,6};
    	int n;
    	scanf("%d",&n);
    	int mid;
    	int left=0;
    	int right=4;
    	while(left<=right){
    		mid=(left+right)/2;
    		if(arr[mid]==a){
    			return mid;
    		}else{
    			if(a<arr[mid]){
    				right=mid-1;
    			}
    			if(a>arr[mid]){
    				left=mid+1;
    			}
    		}
    	}
    	return 0;
    }

**（二）运用范围：返回第一个大于等于n的位置**

#include <stdio.h>
    int main(){
    	int arr[10]={1,3,3,5,5,5,7,9,9,9};
    	int n;
    	scanf("%d",&n);
    	int mid;
    	int left=0;
    	int right=10; //特别注意：这里的上界为10
    	while(left<right){
    		mid=(left+right)/2;
    		if(arr[mid]>=n){
    			right=mid;
    		}else{
    			left=mid+1;
    		}
    	}
    	return left;
    }

**（三）运用范围：返回第一个大于n的位置**

#include <stdio.h>
    int main(){
    	int arr[10]={1,3,3,5,5,5,7,9,9,9};
    	int n;
    	scanf("%d",&n);
    	int mid;
    	int left=0;
    	int right=10;//特别注意：这里的上界为10
    	while(left<right){
    		mid=(left+right)/2;
    		if(arr[mid]>n){
    			right=mid;
    		}else{
    			left=mid+1;
    		}
    	}
    	return left;
    }

**这里重点说明(二）（三）为什么right(上边界)为10：  
这是因为二分的出始区间必须覆盖到所有可能的结果**，因此返回满足条件的位置时，可能不在原数组下标中。  
例如：5个元素\{1，3，3，3，6\}  
查询数字8，因此返回的下标数为5。这里便是上述问题的原因，**因此这个方法是假设序列中存在n**。  
  
所以(二)（三）无法判断是否存在此元素，若想解决此缺陷，增加边界条件做出判断即可。