H指数

cpp
class Solution {
public:
    int hIndex(vector<int>& citations) {
int n = citations.size();

    int left = 0, right = n - 1;

    int hIndex = 0;

    while (left <= right) {

        int mid = left + (right - left) / 2;

        if (citations[mid] >= n - mid) {

            hIndex = n - mid;  // 更新h指数

            right = mid - 1;

        } else {

            left = mid + 1;

        }

    }

    return hIndex;
    }
};

插入位置

cpp
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;

    while (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 left;  // 目标值不存在于数组中，返回它将会被按顺序插入的位置
    }
};

第一个错误的版本

cpp
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
      int left = 1, right = n;

    while (left < right) {

        int mid = left + (right - left) / 2;

        if (isBadVersion(mid)) {

            right = mid;  // 当前版本是错误的，继续在左半部分查找

        } else {

            left = mid + 1;  // 当前版本是正确的，继续在右半部分查找

        }

    }

    return left;  // left和right相等，指向第一个错误的版本  
    }
};

两个数组的交集

cpp
class Solution {
public:
    bool binarySearch(const std::vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
![image.png](/static/img/414b25b903ddb30bc3e9d63d7263b528.image.webp)
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return true;  // 找到目标元素
        } else if (nums[mid] < target) {
            left = mid + 1;  // 目标元素在右半部分
        } else {
            right = mid - 1;  // 目标元素在左半部分
        }
    }
    
    return false;  // 没有找到目标元素
}

std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
    std::sort(nums2.begin(), nums2.end());  // 对nums2进行排序
    std::vector<int> result;
    
    for (int num : nums1) {
        if (binarySearch(nums2, num)) {
            result.push_back(num);  // num在nums2中存在，加入结果数组
        }
    }
    
    std::sort(result.begin(), result.end());  // 对结果数组进行排序
    result.erase(std::unique(result.begin(), result.end()), result.end());  // 去除重复元素
    
    return result;
}
};

排列硬币

cpp
class Solution {
public:
    int arrangeCoins(int n) {
    long left = 1;
    // long rught = n ;
    long right = static_cast<long>(sqrt(2 * static_cast<long long>(n))) + 1;// 适当缩小范围


  
    while (left <= right) {

        long mid = left + (right - left) / 2;

        long totalCoins = mid * (mid + 1) / 2;

        

        if (totalCoins == n) {

            return mid;  // 正好能排满，返回当前行数

        } else if (totalCoins < n) {

            left = mid + 1;  // 硬币总数小于n，在右半部分继续查找

        } else {

            right = mid - 1;  // 硬币总数大于n，在左半部分继续查找

        }

    }

    

    return right;  // 返回硬币总数小于等于n的最大行数
    }
};

猜数字

cpp
class Solution {
public:
    int guessNumber(int n) {
        int left = 1, right = n;

    while (left <= right) {

        int mid = left + (right - left) / 2;

        int result = guess(mid);

        if (result == 0) {

            return mid;

        } else if (result == 1) {

            left = mid + 1;

        } else {

            right = mid - 1;

        }

    }

    return -1; // 如果未找到目标数字，返回 -1 表示异常情况
    }
};

有序数组的单一元素

cpp
#include <vector>

int singleNonDuplicate(std::vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        // 确保 mid 是偶数索引
        if (mid % 2 == 1) {
            mid--;
        }

        // 如果 mid 对应的元素与它的下一个元素相等，说明只出现一次的数在 mid 的右侧
        if (nums[mid] == nums[mid + 1]) {
            left = mid + 2;
        }
        // 否则，只出现一次的数在 mid 的左侧
        else {
            right = mid;
        }
    }

    return nums[left];
}