二分法查找特定值

组别：普及组
难度：4

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

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

一、用for循环实现二分法查找特定值：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-04-07 16:41:39
 * 最后修改: 2025-09-03 00:56:27
 * 文件描述: 二分法查找特定值
****************************************************************/

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {  
        // 注意条件是 <= 区间是闭区间 [left, right]，退出时 left > right。所有元素都在循环里被检查过。
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
    }
    return -1;
}

int binarySearch1(vector<int>& nums, int target) {
    int left = 0, right = nums.size() ; //这里是n，不是n-1
    while (left < right) {  
        // 注意条件是 <,区间是 半开区间 [left, right)，退出时 left ==right。最后一个元素 并没有在循环里被检查。
        int mid = left + (right - left) / 2;
       // if (nums[mid] == target) return mid;     // 过程命中即返回，有这句可以不要最后面的if判断。
        if (nums[mid] < target) left = mid + 1;
           else right = mid;  //  不是mid-1;
    }
    if (left < nums.size() && nums[left] == target) return left;
    return -1;
}

int binarySearch2(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1; //num。size()!=0，否则会产生越界
    while (left < right) {  
        // 注意条件是 <,区间是 半开区间 [left, right)，退出时 left == right。最后一个元素 并没有在循环里被检查。
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
           else if (nums[mid] < target) left = mid + 1;
           else right = mid;  //  不是mid-1;
    }
    if (nums[left] == target) return left; //判断最后一个元素。
    return -1;
}

int main() {
    int n,target;
    cout<<"input nubmer: ";
    cin>>n;
    vector<int> a(n);
    for (int k =0; k < n; ++k) {
        cin>>a[k];
        }
   // sort(a.begin(),a.end());  //如果输入数组不保证升序，就排序。
    cout<<"input number that your want to find: ";
    cin>>target;
    int ans=binarySearch(a,  target);
    //int ans=binarySearch1(a,  target);
    //int ans=binarySearch2(a,  target);
    if(ans==-1){
        cout<<"Element is not present in array";
    }
    else cout<<"the position of the number that you want find in array is "<<ans;
  
    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;
}

练习题目：I1751

P1571_unfinish

洛谷练习：

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

Previous Quiz

Back to Lesson

Next Topic

数据结构与算法

二分法查找特定值