算法基础--二分查找
模板
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
/**
二分查找（Binary Search）是一种高效的查找算法，其时间复杂度为 o(logn)
*/
using namespace std;
const int N = 100010;
int n, q, a[N];
unordered_map<int, int> m;
int main() {
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
m[a[i]] = i; // 修正：将元素索引存入 unordered_map
}
while (q--) {
int x;
scanf("%d", &x);
int R, L;
int l = 0, r = n - 1;
// 二分查找右边界
while (l < r) {
int mid = l + r + 1 >> 1;
if (a[mid] <= x) {
l = mid;
} else {
r = mid - 1;
}
}
R = r; // 二分结束后，l 和 r 相同，共同指向边界
l = 0;
r = n - 1;
// 二分查找左边界
while (l < r) {
int mid = l + r >> 1; // 修正：正确计算 mid
if (a[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
L = r;
if (m.find(x) != m.end()) { // 修正：正确判断元素是否存在
cout << L << " " << R << endl;
} else {
cout << "-1 -1" << endl; // 若元素不存在，输出 -1 -1
}
}
return 0;
}
优化（java)
/**
* @author adwish
* @description 整数二分，用于查询多个元素出现的位置
主要功能是对一个已排序的整数数组进行多次查询，每次查询一个整数 x，
并找出该整数在数组中首次出现和最后一次出现的位置，如果该整数不存在于数组中，则输出 -1 -1。
* @date 2025-02-03 12:54
*/
import java.util.Scanner;
public class IntegerBinary {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取数组长度n和查询次数q
int n = scanner.nextInt();
int q = scanner.nextInt();
// 定义数组并读取元素
int[] a = new int[n];
for (int i = 0; i < a.length; i++) {
a[i] = scanner.nextInt();
}
// 进行查询
for (int i = 0; i < q; i++) {
int x = scanner.nextInt();
int L = findLeftBound(a, x);
int R = findRightBound(a, x);
// 判断元素是否存在数组中
if (L < R && R < n && a[L] == x && a[R] == x) {
System.out.println(L + " " + R);
} else {
System.out.println("-1 -1");
}
}
scanner.close();
}
// 查找左边界
private static int findLeftBound(int[] a, int x) {
int l = 0, r = a.length - 1;
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
// 查找右边界
private static int findRightBound(int[] a, int x) {
int l = 0, r = a.length - 1;
while (l < r) {
int mid = (l + r + 1) / 2; // 防止死循环
if (a[mid] <= x) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
}
练习案例
题目描述35. 搜索插入位置
https://leetcode.cn/problems/search-insert-position/
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l <= r){
int mid = l + (r - l) / 2;//计算中间值的推荐方式，防止溢出
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
l = mid + 1;
} else{
r = mid - 1;
}
}
return l;
}
};题目描述
69. x 的平方根 https://leetcode.cn/problems/sqrtx/
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去
一般解法：
class Solution {
public:
int mySqrt(int x) {
if (x == 0 || x == 1) return x; // 边界条件
int left = 0, right = x;
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid <= x / mid) { // 避免 mid * mid 溢出
result = mid; // 更新结果
left = mid + 1; // 搜索右半部分
} else {
right = mid - 1; // 搜索左半部分
}
}
return result;
}
};
牛顿迭代法
class Solution {
int s;
public int mySqrt(int x) {
s=x;
if(x==0) return 0;
return ((int)(sqrts(x)));
}
public double sqrts(double x){
double res = (x + s / x) / 2;
if (res == x) {
return x;
} else {
return sqrts(res);
}
}
}
数的三次方根（精确）
模板
#include<bits/stdc++.h>
using namespace std;
double n = 0;
int main(){
cin >> n;
double l = -50, r = 50;
while( r - l >= 1e-8)//使l和r精确到1e-6，?要求的多两位，常识！！
{
double mid = (l + r) / 2;
if(mid * mid * mid >= n) r = mid;
else l = mid;
}
printf("%.6f" ,l);
return 0;
}