二分查找

二分查找（Binary Search）

简介

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它通过反复将数组分成两半，然后在其中一半中继续查找，直到找到目标元素或者确定目标元素不在数组中。

满足条件

  • 数组必须有序。（a n-1 ≤ a n 或 a n-1 ≥ a n）
  • 数组中每个元素必须可以随机访问。
  • 数组的上限和下限必须是已知的。

  • 数组有序是二分查找的基本条件，也是是否可以二分的重要依据，每个元素不一定是int类型，每个元素之间能够比较，数组能够排序就行。

  • 为什么每个元素要能随机访问？

    ​ 因为在二分过程中，我们要不断更新左边界指针，右边界指针和中间指针，每次更新都是访问数组里面的某个位置的元素。而链表，要想访问某一个元素，必须先要知道它的前继节点，所以在链表中，你要想遍历某个元素，就要不断遍历之前的节点（既然都遍历之前的元素了，顺便查找了不就行了吗？还用什么二分(／_＼））。像链表、队列、栈等，这些不能随机访问的数据结构，都不能使用二分查找。

  • 关于上限与下限

    ​ 在某种特定的情况下，上限与下限是不容易确定的。只要自己设置的边界能够包含正确答案就可以了（不能超过数据类型的范围）。一般根据情境就能确定。

时间复杂度

二分查找的时间复杂度是O(log n)，其中n是数组的长度。这比线性查找的O(n)要快得多，特别是在处理大型数组时。

二分查找步骤

  1. 确认数组的下限l与上限r。
  2. 确认二分终止条件，while(l+1<r)。
  3. 开始二分 ，int mid = r+l >> 1。（’+‘优先级比’>>‘高，通过右移运算符，可以实现二分，也可以写这个 int mid = (r+l)/2）
  4. 编写bool check(int mid) 函数，check(mid)用于区分数组的边界。（重点）
  5. 更新l和r的值，缩小查找的范围。（重点）
  6. 重复上面3~5步骤，直到不满足条件while(l<r)。
  7. 输出最终结果。

二分查找应用

查找无重复单调有序数组

请查找有序数组{1,3,4,6,8,9,10,16,20,25,44,90,100}里面的元素，输入一个元素n，如果数组中存在此元素，请输出下标，若不存在，请输出-1。

例如：

输入：4

输出：2

或者

输入：5

输出：-1

下面开始解题：

  1. 先判断是否满足二分的条件

    • 元素单调递增，满足有序性。
    • 使用数组存储，满足随机访问。
    • 上限与下限已知。

    满足上面三点，可以使用二分法。

  2. 先创建一个数组接收数据。

    1
    int arr[] ={1,3,4,6,8,9,10,16,20,25,44,90,100};

  3. 确定左边界和右边界，即元素中的下标最小值-1和大于最大值+1。

    1
    2
    int l=-1; //左边界 最小元素下标-1
    int r=sizeof(arr)/sizeof(arr[0]); //右边界，要大于数组的最大下标，该数组最大下标是12，长度是13。
  • 这里的左边界和右边界的范围一定要是[答案左边界-1,答案右边界+1],否则在查找边界元素时，如上面的1或者100，会查找失败(非边界元素不用考虑边界)。

  1. 下面开始二分查找，先把模板写上。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    #include<iostream>
    using namespace std;
    int arr[] ={1,3,4,6,8,9,10,16,20,25,44,90,100};
    int n;
    bool check(int mid) //编写check(mid)函数
    {
    	
    } 
    int main()
    {
    	cin>>n;// 接收要查找的元素n 
    	int l=-1; //左边界 
    	int r=sizeof(arr)/sizeof(arr[0]); //右边界，即数组的最大下标 
    	while(l+1<r)//二分终止条件
    	{
    		int mid = l + r >> 1;//也可以写 int mid = (l+r)/2;
    		if(check(mid))// 边界更新条件，根据题意写
    		{
    			
    		}else
    		{
    			
    		}	
    	} 
    }

    基本所有的二分查找都适用上面这套模板，多理解理解，背一背。

  2. 编写check(mid)函数和更新l与r的边界（重点）。

    假如我们要查找元素‘4’。

    我们先看一下，当前l和r所指向的位置:

    第一次进入while(l+1<r)，第一次执行 int mid = l + r >> 1 ，此时mid = -1+ 13 >> 1 = 6

    此时，发现要查找的元素‘4’在mid指针的左侧，现在元素‘4’在一个新的区间内(l,mid)，arr[l]<4<arr[mid]，所以我们要移动r指针，指向mid，即r=mid。

    -

    再次更新mid的值：mid = l+r>>1=-1+6>>1=2，arr[mid]=4,我们就找到了元素‘4’，并且元素‘4’的下标就是2。

    已经找到了元素‘4’的下标，但是while(l+1<r)，循序没有退出，所以还需要更新l和r的位置，此时更新左边界l和更新右边界r都是可以的。

    • 如果更新左边界，使目标元素最终在左边界上，我们称为“答案在左边界上” 。
    • 如果更新右边界，使目标元素最终在右边界上，我们称为“答案在右边界上” 。

    这是两种不同的写法，不同的写法会导致下面更新l和r不同，哪一种写法都可以解决问题。

    答案在左边界上

    ​

    答案都在左边界上了，那么左边界在更新的时候，就要考虑答案是否在左边界上了。所以给l赋值的时候，范围要包含目标元素。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    bool check(int mid) //编写check(mid)函数。
    {
    	if(arr[mid]<=n)//只要能分成上面两部分就行，if(arr[mid]>n)也可以。
    	{
    		return true;
    	}else
    	{
    		return false;
    	 }
    }

    根据上面check(mid)函数，就可以更新l和r了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    while(l+1<r)
    {
    	int mid = l + r >> 1; 
    	if(check(mid))
    	{
    		l=mid;
    	}
    	else
    	{
    		r=mid;
    	}	
    }

    答案在右边界上

    答案都在右边界上了，那么右边界在更新的时候，就要考虑答案是否在右边界上了。所以给r赋值的时候，范围要包含目标元素。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    bool check(int mid) //编写check(mid)函数。
    {
    	if(arr[mid]>=n)//只要能分成上面两部分就行，if(arr[mid]>n)也可以。
    	{
    		return true;
    	}else
    	{
    		return false;
    	 }
    }

    根据上面check(mid)函数，就可以更新l和r了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    while(l+1<r)
    {
    	int mid = l + r >> 1; 
    	if(check(mid))
    	{
    		r=mid;
    	}
    	else
    	{
    		l=mid;
    	}	
    }

  3. 是否找到了目标元素，并输出结果。

    “答案在左边界上”完整代码 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    //答案在左边界上
    #include<iostream>
    using namespace std;
    int arr[] ={1,3,4,6,8,9,10,16,20,25,44,90,100};
    int n;
    bool check(int mid) //编写check(mid)函数
    {
    	if(arr[mid]<=n)
    	{
    		return true;
    	}else
    	{
    		return false;
    	 } 
    } 
    int main()
    {
    	cin>>n;// 接收要查找的元素n 
    	int l=-1; //左边界 
    	int r=sizeof(arr)/sizeof(arr[0]); //右边界，即数组的最大下标 
    	while(l+1<r)
    	{
    		int mid = l + r >> 1;
    		if(check(mid)) //技巧：答案在哪个边界上，为true，就更新哪个边界
    		{
    			l=mid;
    		}
    		else
    		{
    			r=mid;
    		}	
    	} 
    	if(arr[l]==n)//判断左边界上，是否为要查的元素 
    	{
    		cout<<l; 
    	}
    	else
    	{
    		cout<<-1;
    	} 
    }
    “答案在右边界上”完整代码 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    //答案在右边界上
    #include<iostream>
    using namespace std;
    int arr[] ={1,3,4,6,8,9,10,16,20,25,44,90,100};
    int n;
    bool check(int mid) //编写check(mid)函数
    {
    	if(arr[mid]>=n)
    	{
    		return true;
    	}else
    	{
    		return false;
    	 } 
    } 
    int main()
    {
    	cin>>n;// 接收要查找的元素n 
    	int l=-1; //左边界 
    	int r=sizeof(arr)/sizeof(arr[0]); //右边界，即数组的最大下标 
    	while(l+1<r)
    	{
    		int mid = l + r >> 1;
    		if(check(mid))//技巧：答案在哪个边界上，为true，就更新哪个边界
    		{
    			r=mid;
    		}
    		else
    		{
    			l=mid;
    		}	
    	} 
    	if(arr[r]==n)//判断右边界上，是否为要查的元素 
    	{
    		cout<<r; 
    	}
    	else
    	{
    		cout<<-1;
    	} 
    }

二分查找拓展

查找单调不递增或递减有序数组

请查找单调不递减有序数组{2,4,7,7,7,7,8,8,9,9,9,10,16,16,32,50}里面的元素，输入一个元素n，如果数组中存在此元素，请输出该元素的最小下标和最大下标，若不存在，请输出-1。

例如：

输入：4

输出：1 1

或者

输入：9

输出：8 10

或者

输入：11

输出：-1

下面开始解题：

  1. 先判断是否满足二分的条件

    • 元素单调递增，满足有序性。
    • 使用数组存储，满足随机访问。
    • 上限与下限已知。

    满足上面三点，可以使用二分法。

  2. 先创建一个数组接收数据。

    1
    int arr[] ={2,4,7,7,7,7,8,8,9,9,9,10,16,16,32,50};

  3. 确定左边界和右边界，即元素中的小于最小值和大于最大值。

    1
    2
    int l=-1; //左边界 要小于0
    int r=sizeof(arr)/sizeof(arr[0]); //右边界，要大于数组的最大下标

  4. 先把模板写上，之后再补全。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    #include<iostream>
    using namespace std;
    int arr[] ={2,4,7,7,7,7,8,8,9,9,9,10,16,16,32,50};
    int n;
    bool check(int mid) //编写check(mid)函数
    {
    	
    } 
    int main()
    {
    	cin>>n;// 接收要查找的元素n 
    	int l=-1; //左边界 
    	int r=sizeof(arr)/sizeof(arr[0]); //右边界，即数组的最大下标 
    	while(l+1<r)
    	{
    		int mid = l + r >> 1;
    		if(check(mid))
    		{

    		}
    		else
    		{

    		}	
    	} 
    }

  5. 编写check(mid)函数和更新l与r的边界（重点）。

    假如我们要查找元素‘9’。

    我们先看一下，当前l和r所指向的位置:

    check(mid)函数必须能够，区分目标元素的左右边界，所以可以这样分。

    • 第一种分法：答案在右边界上 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    bool check(int mid) 
    {
    	if(arr[mid]>=n)
    	{
    		return true;
    	}else
    	{
    		return false;
    	 } 
    }

    • 第二种分法：答案在左边界上 

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      bool check(int mid) 
      {
      	if(arr[mid]<=n)
      	{
      		return true;
      	}else
      	{
      		return false;
      	 } 
      }
      • 在查找单调不递增或递减有序数组 中:
      • 查找目标元素的最小下标使用：答案在右边界上法 。
      • 查找目标元素的最大下标使用：答案在左边界上法 。

  6. 找到目标元素，输出结果。

    完整代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    #include<iostream>
    using namespace std;
    int arr[] ={2,4,7,7,7,7,8,8,9,9,9,10,16,16,32,50};
    int n;
    int save_l,save_r;//保存左边界和右边界 
    bool checkOnRight(int mid) //答案在右边界上
    {
    	if(arr[mid]>=n)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	} 
    } 
    bool checkOnLeft(int mid) //答案在左边界上 
    {
    	if(arr[mid]<=n)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	} 
    }
    int main()
    {
    	cin>>n;// 接收要查找的元素n 
    	int l=-1; //左边界 
    	int r=sizeof(arr)/sizeof(arr[0]); //右边界，即数组的最大下标 
    	//先找左边界 ，采用“答案在右边界法” 
    	while(l+1<r)
    	{
    		int mid = l + r >> 1;
    		if(checkOnRight(mid)) //答案在右边法 
    		{
    			r=mid;
    		}
    		else
    		{
    			l=mid;
    		}	
    	}
    	save_l=r; //保存左边界 
    	if(arr[save_l]==n) //找到了目标元素的最小下标 
    	{
    		//之后找右边界 ，采用“答案在左边界法” 
    		l=-1; //其实这里可以为l=save_l-1，因为上面的save_l就是n的左边界，这样可以缩小范围 
    		r=sizeof(arr)/sizeof(arr[0]);//右边界 
    		while(l+1<r)
    		{
    			int mid = l + r >> 1;
    			if(checkOnLeft(mid)) //答案在左边法 
    			{
    				l=mid;
    			}
    			else
    			{
    				r=mid;
    			}	
    		} 
    		save_r=l;//保存右边界 
    		if(arr[save_r]==n)//找到了目标元素的最大下标 ,上面已经验证最小下标了，故不需要验证了。 
    		{
    			cout<<save_l<<" "<<save_r; 
    		} 
    	}
    	else // 没有找到 
    	{
    		cout<<"-1";
    	}
    	return 0;
    }
    上面代码的封装版 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    //封装版(可改变参数，可读性高)
    #include<iostream>
    using namespace std;
    int getMinPos(int l,int r,int arr[],int n)//获取目标元素的最小下标 
    {
    	while(l+1<r)
    	{
    		int mid = l+r>>1;
    		if(arr[mid]>=n)
    		{
    			r=mid;	
    		}else
    		{
    			l=mid;
    		}
    	}
    	return arr[r]==n?r:-1;
    }
    int getMaxPos(int l,int r,int arr[],int n)//获取目标元素的最大下标 
    {
    	while(l+1<r)
    	{
    		int mid = l+r>>1;
    		if(arr[mid]<=n)
    		{
    			l=mid;	
    		}else
    		{
    			r=mid;
    		}
    	}
    	return arr[l]==n?l:-1;
    }
    int main()
    {
    	int arr[] ={2,4,7,7,7,7,8,8,9,9,9,10,16,16,32,50};
    	int n; 
    	cin>>n;// 接收要查找的元素n 
    	int l=-1; //左边界 
    	int r=sizeof(arr)/sizeof(arr[0]); //右边界，即数组的最大下标 
    	int save_l=getMinPos(l,r,arr,n); 
    	int save_r=getMaxPos(save_l-1,r,arr,n);//这么写是为了缩小范围，也可以写getMaxPos(l,r,arr,n); 
    	if(save_l!=-1)//只要save_l和save_r其中一个不是-1，另一个肯定不是-1，只要能找到最小下标，也就存在最大下标。 
    	{
    		cout<<save_l<<" "<<save_r;	
    	}else
    	{
    		cout<<-1;
    	}
    	return 0;
    }
    如果给一个单调不递增有序数组，还能使用这个方法吗？

    • 本质上获取目标元素最小下标还是使用答案在右边界上法，最大下标是答案在左边界上法。

    • 举例：给定一个单调不递增有序数组{10,9,8,8,8,8,5,2,1,0}，请输出指定元素n的最小下标和最大下标，否则输出-1。

      为什么还能使用“答案在右边界法”和“答案在左边界法”呢？请看下图：

      虽然数组元素的顺序改变了，但是仍然是有序的，具有边界性质的，所以只需改变check(mid)里面的条件就好了，改的地方我会标注一下，仔细对比一下。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    #include<iostream>
    using namespace std;
    int arr[] ={10,9,8,8,8,8,5,2,1,0};
    int n;
    int save_l,save_r;//保存左边界和右边界 
    bool checkOnRight(int mid) //答案在右边界上
    {
    	if(arr[mid]<=n) //这里改了
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	} 
    } 
    bool checkOnLeft(int mid) //答案在左边界上 
    {
    	if(arr[mid]>=n)  //这里也改了
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	} 
    }
    int main()
    {
    	cin>>n;
    	int l=-1; //左边界 
    	int r=sizeof(arr)/sizeof(arr[0]); 
    	while(l+1<r)
    	{
    		int mid = l + r >> 1;
    		if(checkOnRight(mid)) 
    		{
    			r=mid;
    		}
    		else
    		{
    			l=mid;
    		}	
    	}
    	save_l=r; 
    	if(arr[save_l]==n)  
    	{

    		l=-1; 
    		r=sizeof(arr)/sizeof(arr[0]);
    		while(l+1<r)
    		{
    			int mid = l + r >> 1;
    			if(checkOnLeft(mid)) 
    			{
    				l=mid;
    			}
    			else
    			{
    				r=mid;
    			}	
    		} 
    		save_r=l;
    		if(arr[save_r]==n)
    		{
    			cout<<save_l<<" "<<save_r; 
    		} 
    	}
    	else
    	{
    		cout<<"-1";
    	}
    	return 0;
    }

    ​

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    //封装版
    #include<iostream>
    using namespace std;
    int getMinPos(int l,int r,int arr[],int n)//获取目标元素的最小下标 
    {
    	while(l+1<r)
    	{
    		int mid = l+r>>1;
    		if(arr[mid]<=n) //这里改了 
    		{
    			r=mid;	
    		}else
    		{
    			l=mid;
    		}
    	}
    	return arr[r]==n?r:-1;
    }
    int getMaxPos(int l,int r,int arr[],int n)//获取目标元素的最大下标 
    {
    	while(l+1<r)
    	{
    		int mid = l+r>>1;
    		if(arr[mid]>=n) //这里也改了 
    		{
    			l=mid;	
    		}else
    		{
    			r=mid;
    		}
    	}
    	return arr[l]==n?l:-1;
    }
    int main()
    {
    	int arr[] ={10,9,8,8,8,8,5,2,1,0};
    	int n; 
    	cin>>n;
    	int l=-1; 
    	int r=sizeof(arr)/sizeof(arr[0]); 
    	int save_l=getMinPos(l,r,arr,n); 
    	int save_r=getMaxPos(save_l-1,r,arr,n);
    	if(save_l!=-1)
    	{
    		cout<<save_l<<" "<<save_r;	
    	}else
    	{
    		cout<<-1;
    	}
    	return 0;
    }