二分法(1)——定义及基础用法

0.二分法简介

• 二分法是一种查找算法
• 要求：数据必须是有序序列
• 核心思想：掐头去尾取中间

---

1. 引入

对于一个有序数组，如{1，3，6，8，23，56，78，99}，如果我们要查找其中的一个数78的下标位置，按照以前的写法，可能会这么写

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	int a[]={1,3,6,8,23,56,78,99},target;// 定义数组和要查找的目标 
	int len= sizeof(a)/sizeof(int);
	cin>>target;
	for(int i=0;i<len;i++)
	{
	 	if(a[i]==target)
	 		{
				cout<<i<<endl;
				return 0; 
			}
	} 
	return 0;
} 

这种顺序查找的方式对于数据量较小的情况还可以应付，但是对于数据量大的情况就很难处理了。试想一下特殊情况，如果你要查找的值正好在数组的最后一个，那么你的时间复杂度就是O(n)。所以引入二分查找来解决这个问题。

如果上面的题目用二分法求解，可以参考下面代码。（题目保证有解的情况下）

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	int a[]={1,3,6,8,23,56,78,99},target;// 定义数组和要查找的目标 
	int len,left,right,mid;//定义长度，左端点，右端点，中间 
	right = sizeof(a)/sizeof(int); //右端点 
	left=0; //左端点 
	mid=(left+right)/2;  //中间 
	cin>>target;
	while(a[mid] !=target)
	{
		if(a[mid] > target)
			right=mid;
		else
			left = mid;
		mid=(left+right)/2;	
	} 
	cout<<mid;
	
	return 0;
} 

---

2.二分法求解

例题1

【描述】给定一个排序的整数数组（升序）和一个要查找的整数target，找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。【输入描述】输入包含三行，第一行n,表示有n个数，第二行是已经排好序的n个数
第三行是target【输出描述】一行，target第一次出现的下标，如果没有找到输出-1。【样例输入1】
6
1 4 6 7 9 11
4【样例输出1】
1【样例输入2】
7
1 2 6 8 9 12 78
4【样例输出1】
-1

---

【注意】题目不一定有解，可以遵循下面的算法框架

while (left < right - 1) {
	int mid = left + (right - left) / 2;
	//添加结束条件 
	
	// 
	if (A[mid] > A[left]) {
		left = mid;
	} else {
		right = mid;
	}
}

【参考代码】

#include<cstdio>
#include<iostream>
using namespace std;
int search(int A[], int n, int target)  
{  
    int left = 0, right = n-1;  
    while(left <= right)  
    {  
        // 注意：若使用(low+high)/2求中间位置容易溢出  
        int mid = left+((right-left)>>1);   
        if(A[mid] == target)  
            return mid;  
        else if(A[mid] < target)  
            left = mid+1;  
        else // A[mid] > target  
            right = mid-1;  
    }  
    return -1;  
}  
int main()
{
	int a[100]={0},target;// 定义数组和要查找的目标
	int len,n,index;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];	
	}	
	cin>>target;
	index = search(a,n,target); 
	cout<<index;
	return 0;
} 

例题2

【描述】给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1【输入描述】输入包含三行，第一行n,表示有n个数，第二行是已经排好序的n个数
第三行是target【输出描述】一行，target最后一次出现的下标，如果没有找到输出-1。

---

返回目录：算法

---