二分查找法

组别：普及组
难度：4

二个小朋友玩猜数字的游戏，其中一个小朋友写下一个数字，其一个小朋友猜，每次第一个小朋友都会回答是大了还是小了。请问第二个小朋友能保证多少次内猜中吗？

在⽤⼆分法进⾏查找时，查找对象的数组必须是有序的，即各数组元素的次序是按其值的⼤⼩顺序存储的。其基本思想是先确定待查数
据的范围（可⽤ [left,right] 区间表⽰），然后逐步缩⼩范围直到找到或找不到该记录为⽌。具体做法是：先取数组中间位置（mid=(left+right)/2）的数据元素与给定值⽐较。若相等，则查找成功；否则，若给定值⽐该数据元素的值⼩（或⼤），则给定值必在数组的前半部分[left,mid-1]（或后半部分[mid+1,right]），然后在新的查找范围内进⾏同样的查找。如此反复进⾏，直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为⽌。因此，⼆分查找每查找⼀次，或成功，或使查找数组中元素的个数减少⼀半，当查找数组中不再有数据元素时，查找失败。

一、用for循环实现二分法代码：

/**************************************************************** 
 * Description: Binary Search by using loop if(l<=r)
 * Author: Alex Li
 * Date: 2024-01-27 20:07:40
 * LastEditTime: 2024-04-07 18:57:42
****************************************************************/
#include <iostream>
using namespace std;
int main() {
    int n,ans;
    cout<<"input nubmer:"<<endl;
    cin>>n;
    vector<int> a(n);
    for (int k =0; k < n; ++k) {
        cin>>a[k];
        }
    cout<<"input number that your want to find:"<<endl;
    cin>>ans;
    int mid,l=0,r=n-1;
    while(l<=r){
        mid=l+(r-l)/2;
        if(a[mid]==ans){
            cout<<"the position of the number that you want to find in array is "<<mid;
            return 0;
        }
        if(a[mid]>ans)r=mid-1;
        else l=mid+1; 
    }
        cout<<"Element is not present in array";
    return 0;
}

二、用递归实现二分法：

/**************************************************************** 
 * Description: binary search by using recursion if(l<=r)
 * Author: Alex Li
 * Date: 2022-09-01 08:59:18
 * LastEditTime: 2024-04-07 19:01:25
****************************************************************/
#include <iostream>
using namespace std;
vector<int> arr;

int binarySearch(int left, int right, int x){
	if (left<=right) {
		int mid = left + (right - left) / 2;
		      	if (arr[mid] == x)
			return mid;
		if (arr[mid] > x)   
			return binarySearch(left, mid-1, x);
		else     
			return binarySearch(mid + 1, right, x);
	}
	return -1;
}

int main(void){
	int n,x;
	cout<<"input number:"<<endl;
    cin>>n;
	arr.resize(n);
    for (int i = 0; i <n; i++){
        cin>>arr[i];
    }
    cout<<"input number that your want to find:"<<endl; 
    cin>>x;
	int result = binarySearch(0, n - 1, x);
	if(result == -1)
		 cout << "Element is not present in array";
	else
		 cout<<"the position of the number that you want to find in array is "<<result;
	return 0;
}

三、更改判断条件 (l<r)

/**************************************************************** 
 * Description: binary search if(l<r)
 * Author: Alex Li
 * Date: 2024-01-27 20:07:40
 * LastEditTime: 2024-04-07 18:43:35
****************************************************************/
#include <iostream>
using namespace std;
int main() {
    int n,ans;
    cout<<"input nubmer:"<<endl;
    cin>>n;
    vector<int> a(n);
    for (int k =0; k < n; ++k) {
        cin>>a[k];
        }
    cout<<"input number that your want to find: "<<endl;
    cin>>ans;
    int mid,l=0,r=n; //不是r=n-1
    while(l<r){  //更改判断条件
        mid=l+(r-l)/2;
        if(a[mid]==ans){
            cout<<"the position of the number that you want find in array is "<<mid;
            return 0;
        }
        if(a[mid]>ans)r=mid;  //不是r=mid-1
        else l=mid+1; 
    }
        cout<<"Element is not present in array";
    return 0;
}

练习题目：I1751

P1571_unfinish

洛谷练习：

P1571, P1824, P2440, P2005, P1873, P1661, P2658, P1083, P1883

Previous Quiz

Back to Lesson

Next Topic

数据结构与算法

二分查找法