#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	//vector<int> nums = {1, 3, 5, 5, 7, 9};
	//auto it = lower_bound(nums.begin(), nums.end(), 5);
	//vector<int>::iterator it = lower_bound(nums.begin(), nums.end(), 5);
	//if (it != nums.end()) {
	//	cout << "第一个不小于5的元素是: " << *it << endl;  // 输出: 5
	//	cout << "索引: " << (it - nums.begin()) << endl;  // 输出: 2
	//}
	vector<int> nums = {1, 3, 5, 5, 7, 9};
	auto it = upper_bound(nums.begin(), nums.end(), 5);
	if (it != nums.end()) {
		cout << "第一个大于5的元素是: " << *it << endl;  // 输出: 7
		cout << "索引: " << (it - nums.begin()) << endl;  // 输出: 4
	}
	return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	vector<int> nums = {1, 3, 5, 5, 7, 9};
	//auto it = lower_bound(nums.begin(), nums.end(), 5);
	vector<int>::iterator it = lower_bound(nums.begin(), nums.end(), 5);
	if (it != nums.end()) {
		cout << "第一个不小于5的元素是: " << *it << endl;  // 输出: 5
		cout << "索引: " << (it - nums.begin()) << endl;  // 输出: 2
	}
	return 0;
}

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

int upperBound1(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	//int ans = nums.size();
	
	while (left <= right) {
		int mid = left + (right - left) / 2;
		
		if (nums[mid] > target) {
			//ans = mid;
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	if(left == nums.size()){
		return -1;
	}
	return left;
}
int upperBound2(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	int ans = -1;//nums.size();
	
	while (left <= right) {
		int mid = left + (right - left) / 2;
		
		if (nums[mid] > target) {
			ans = mid;
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	
	return ans;
}


int main() {
	vector<int> nums = {1, 3,4,4,4,5, 5, 7, 9};
	int i = upperBound1(nums,4);
	cout <<  nums[i]<<" "<<i<< endl;
	
	return 0;
}

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

int lowerBound1(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	//int ans = -1; // 默认返回 size 表示都比 target 小
	
	while (left <= right) {
		int mid = left + (right - left) / 2;
		
		if (nums[mid] >= target) {
			//ans = mid;
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	
	//return ans;
	if(left == nums.size()){
		return -1;
	}
	return left;
}
int lowerBound2(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	int ans = -1;
	
	while (left <= right) {
		int mid = left + (right - left) / 2;
		
		if (nums[mid] >= target) {
			ans = mid;
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	
	return ans;
}

int main() {
	vector<int> nums = {1, 3,4,4,4,5, 5, 7, 9};
	int i = lowerBound2(nums,6);
	cout <<  nums[i]<<" "<<i<< endl;
	
	return 0;
}

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

int lowerBound(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	//int ans = -1; // 默认返回 size 表示都比 target 小
	
	while (left <= right) {
		int mid = left + (right - left) / 2;
		
		if (nums[mid] >= target) {
			//ans = mid;
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	
	//return ans;
	if(left == nums.size()){
		return -1;
	}
	return left;
}

int main() {
	vector<int> nums = {1, 3,4,4,4,5, 5, 7, 9};
	int i = lowerBound(nums,-99);
	cout <<  nums[i]<<" "<<i<< endl;
	
	return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> nums = {1, 3, 5, 7, 9};

int main() {
	bool exists = binary_search(nums.begin(), nums.end(), 5);
	cout << (exists ? "存在" : "不存在") << endl;  // 输出: 存在
	
	return 0;
}

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int target) {
	int left = 0;
	int right = n - 1;
	
	while (left <= right) {
		int mid = (left +right ) / 2; 
		
		if (arr[mid] == target)
			return mid;
		else if (arr[mid] < target)
			left = mid + 1;
		else
			right = mid - 1;
	}
	
	return -1; // 没有找到
}

int main() {
	int arr[] = {1, 3, 5, 7, 9, 11, 13};
	int n = sizeof(arr) / sizeof(arr[0]);
	int target = 9;
	
	int index = binarySearch(arr, n, target);
	
	if (index != -1)
		cout << "找到了！下标为：" << index << endl;
	else
		cout << "没有找到这个数。" << endl;
	
	return 0;
}

🔍 二分查找最坏情况查找次数公式详解 🧮

📈 理解查找次数的数学原理，轻松掌握算法效率！

✅ 一、什么是二分查找？

二分查找（Binary Search） 是一种高效的查找算法，适用于有序数组。它通过不断将查找区间对半分，逐步缩小搜索范围。

💡 二、最坏情况指的是什么？

最坏情况（Worst Case）：目标元素在数组中不存在，或者刚好位于最后一次比较的位置。

在这种情况下，我们需要最多次分割数组才能确定结果。

📘 三、核心公式：最坏查找次数

⚙️ 公式如下：

或写作：

这两个公式是等价的，都可以用来计算最坏情况下需要多少次比较。

🧮 四、公式的通俗解释

• $\log_2 n$：表示你要把一个长度为 n 的数组对半分几次才能只剩一个元素。
• $\lfloor \log_2 n \rfloor + 1$：向下取整后加1，是因为即使最后只剩一个元素，也需要一次比较来确认。
• $\lceil \log_2 (n+1) \rceil$：向上取整是为了考虑边界情况，比如正好落在最后一层。

📊 五、举例说明

🧠 六、为什么是这个公式？

想象你有一个长度为 $n$ 的数组：

• 第一次查找后剩下 $\frac{n}{2}$
• 第二次剩下 $\frac{n}{4}$
• ……
• 最后剩下 1 个元素时停止

总共比较的次数就是你把 $n$ 不断除以 2 直到小于等于 1 的次数。

这就是 $\log_2 n$ 的含义。

🎁 七、鼓励语 💪

👋 同学，恭喜你掌握了二分查找最坏情况下的数学规律！这不仅是编程中的基本功，更是你在蓝桥杯、GESPC、CSP等竞赛中提升效率的关键武器！

🧠 学会了这个公式，你就能够快速判断在不同规模数据下算法的表现，从而写出更高效、更聪明的程序！
🚀 继续加油，坚持练习，你一定能成为算法高手！

🎉 每一次调试和优化，都是你成长的足迹。我们在这里为你打call！👏👏👏

📅 最后更新时间：2025年5月23日 1:35

🎉 祝你学习愉快，早日成为编程高手！💪

二分查找的时间复杂度是 O(log n)，其中 n 是被查找数组的长度。最坏情况下的查找次数等于将该数组反复对半分割直到找到目标或确定目标不存在所需要的次数。这个次数可以通过计算 log₂(n) 来得到，即以2为底n的对数，并向上取整（因为即使是最接近的下一次分割也会算作一次操作）。

下面是对于大小分别为 10, 100, 1000 等等一直到 10 亿的数组，在最坏情况下进行二分查找需要的最大尝试次数：

请注意，上面的查找次数是基于向上取整的原则得出的。例如，对于大小为10的数组，log₂(10) 大约是 3.32，所以我们取 4 次作为最坏情况下的查找次数。同样地，对于大小为100的数组，log₂(100) 大约是 6.64，因此我们取 7 次。以此类推。这些数值反映了在完全有序且均匀分布的数据集上应用二分查找时，理论上最多需要比较的次数。

🔍 C++二分查找完全教程：从原理到实战

🌟 欢迎进入高效查找的世界

在编程中，查找数据是最常见的操作之一。想象一下，在一本厚厚的字典中找一个单词，你会从头翻到尾吗？当然不会！你会直接根据字母顺序翻到对应的页面，这就是二分查找的思想。今天我们就来学习这种高效的查找算法！

🧩 什么是二分查找？

二分查找（Binary Search），也叫折半查找，是一种在有序数组中查找特定元素的高效算法。它的核心思想是：

1. 将数组分成两半
2. 比较中间元素与目标值
3. 根据比较结果，在左半部分或右半部分继续查找
4. 重复以上步骤，直到找到目标值或确定目标值不存在

🌰 生活中的二分查找比喻

就像在字典中查找"apple"：

1. 打开字典中间页，发现是"middle"
2. "apple"在"middle"前面，所以翻到前半部分
3. 找到中间页是"good"，"apple"还在前面
4. 继续翻到前半部分的中间页，直到找到"apple"

这种方法比从头翻到尾快得多！

📊 二分查找 vs 顺序查找

🛠️ C++实现二分查找

🔧 方法一：迭代实现（推荐）

#include <iostream>
#include <vector>
#include <algorithm>  // 用于sort函数
using namespace std;

// 在有序数组中查找目标值，返回索引，不存在返回-1
int binarySearch(vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    
    while (left <= right) {
        // 计算中间位置，使用(left + right) / 2可能溢出，推荐写法：
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;  // 找到目标值，返回索引
        } else if (arr[mid] < target) {
            left = mid + 1;  // 目标值在右半部分
        } else {
            right = mid - 1;  // 目标值在左半部分
        }
    }
    
    return -1;  // 未找到目标值
}

int main() {
    vector<int> numbers = {12, 18, 25, 36, 42, 55, 63, 77, 89, 95};
    int target;
    
    // 先排序（虽然数组已经有序，但养成习惯）
    sort(numbers.begin(), numbers.end());
    
    cout << "数组元素：";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    cout << "请输入要查找的目标值：";
    cin >> target;
    
    int index = binarySearch(numbers, target);
    
    if (index != -1) {
        cout << "找到目标值 " << target << "，索引为 " << index << endl;
    } else {
        cout << "未找到目标值 " << target << endl;
    }
    
    return 0;
}

🔧 方法二：递归实现

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

// 递归版二分查找
int binarySearchRecursive(vector<int>& arr, int target, int left, int right) {
    if (left > right) {
        return -1;  // 未找到
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}

int main() {
    vector<int> numbers = {5, 10, 15, 20, 25, 30, 35, 40, 45};
    int target;
    
    sort(numbers.begin(), numbers.end());
    
    cout << "数组元素：";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    cout << "请输入要查找的目标值：";
    cin >> target;
    
    int index = binarySearchRecursive(numbers, target, 0, numbers.size() - 1);
    
    if (index != -1) {
        cout << "找到目标值 " << target << "，索引为 " << index << endl;
    } else {
        cout << "未找到目标值 " << target << endl;
    }
    
    return 0;
}

🔍 二分查找的执行过程

以数组[1, 3, 5, 7, 9, 11, 13]查找7为例：

1. 初始状态：left=0, right=6, mid=3

   [1, 3, 5, 7, 9, 11, 13]
        ^
       mid=3, arr[mid]=7，找到！
   

   只需1次比较即可找到。

查找11的过程：

1. 第一次：left=0, right=6, mid=3, arr[mid]=7 < 11 → left=4

   [1, 3, 5, 7, 9, 11, 13]
                ^
       mid=3, arr[mid]=7 < 11，查看右半部分
   

2. 第二次：left=4, right=6, mid=5, arr[mid]=11 → 找到！

   [1, 3, 5, 7, 9, 11, 13]
                    ^
       mid=5, arr[mid]=11，找到目标值
   

   共2次比较。

🧩 二分查找的边界条件

二分查找中最容易出错的就是边界条件处理，以下是关键要点：

1. 循环条件：while (left <= right) 还是 while (left < right)？

   • 前者适用于需要返回具体索引的情况
   • 后者适用于查找特定区间，需要配合返回值处理

2. mid的计算：left + (right - left) / 2 避免溢出

   • (left + right) / 2 在left和right很大时可能导致整数溢出

3. 更新left和right：

   • 找到目标值时：直接返回
   • 目标值大于mid时：left = mid + 1
   • 目标值小于mid时：right = mid - 1

🚀 实战：在旋转有序数组中查找

问题描述：

数组是有序的，但进行了一次旋转（如[4,5,6,7,0,1,2]），在其中查找目标值。

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

// 在旋转有序数组中查找目标值
bool search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return true;
        }
        
        // 左半部分有序
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } 
        // 右半部分有序
        else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return false;
}

int main() {
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    int target;
    
    cout << "数组元素：";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    cout << "请输入要查找的目标值：";
    cin >> target;
    
    if (search(nums, target)) {
        cout << "找到目标值 " << target << endl;
    } else {
        cout << "未找到目标值 " << target << endl;
    }
    
    return 0;
}

💡 二分查找的变种应用

1. 查找第一个等于目标值的元素

int findFirstEqual(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;  // 记录当前位置
            right = mid - 1;  // 继续在左半部分查找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

2. 查找最后一个等于目标值的元素

int findLastEqual(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;  // 记录当前位置
            left = mid + 1;  // 继续在右半部分查找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

3. 查找第一个大于目标值的元素

int findFirstGreater(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] > target) {
            result = mid;  // 记录当前位置
            right = mid - 1;  // 继续在左半部分查找更小的
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

⚙️ C++标准库中的二分查找函数

C++标准库提供了方便的二分查找函数，位于<algorithm>头文件中：

1. binary_search：判断是否存在

vector<int> nums = {1, 3, 5, 7, 9};
bool exists = binary_search(nums.begin(), nums.end(), 5);
cout << (exists ? "存在" : "不存在") << endl;  // 输出: 存在

2. lower_bound：查找第一个不小于目标值的元素

vector<int> nums = {1, 3, 5, 5, 7, 9};
auto it = lower_bound(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    cout << "第一个不小于5的元素是: " << *it << endl;  // 输出: 5
    cout << "索引: " << (it - nums.begin()) << endl;  // 输出: 2
}

3. upper_bound：查找第一个大于目标值的元素

vector<int> nums = {1, 3, 5, 5, 7, 9};
auto it = upper_bound(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    cout << "第一个大于5的元素是: " << *it << endl;  // 输出: 7
    cout << "索引: " << (it - nums.begin()) << endl;  // 输出: 4
}

🌟 总结与鼓励

恭喜你完成了二分查找的学习！现在你已经掌握了：

1. 二分查找的基本原理和思想
2. 迭代和递归两种实现方式
3. 边界条件的处理技巧
4. 标准库中的二分查找函数
5. 多种变种应用场景

二分查找是算法中的基础利器，它的思想可以应用到很多复杂问题中。刚开始可能会觉得边界条件处理很麻烦，但只要多练习，一定能熟练掌握！

📚 拓展学习

• 学习三分查找，用于单峰函数的极值查找
• 深入理解二分查找在排序算法（如插入排序优化）中的应用
• 尝试解决LeetCode上的二分查找相关题目
• 研究二分查找在大数据处理中的应用场景

记住，编程的进步源于不断的实践。继续加油，你一定能在算法的世界里畅游！ 🔍🚀