Logo Jay's Blog
  • 首頁
  • 關於
  • 最近文章
  • 文章
Logo Inverted Logo
  • 标签
  • Algorithm
  • Array
  • Binary-Search
  • Combinatorics
  • Docker
  • Dynamic-Programming
  • Git
  • Github
  • Github-Action
  • Homelab
  • Leetcode
  • Linux
  • Opencv
  • Openwrt
  • Raspberry-Pi
  • Raspberry-Pi-3
  • Raspberry-Pi-4
  • String
  • Synology
  • Vpn
  • Yolo
Hero Image
Binary Search 中的 lower bound & upper bound

前言

c++ 的 STL 有提供兩個跟 binary seach 有關的 function: lower_bound 和 upper_bound, 每次在寫 leetcode 相關的題目時都會一直忘記這兩個 function 的定義,故決定紀錄一下兩者的定義及用法

Include STL

lower_bound 和 upper_bound 被定義在 <algorithm> 裡面

#include <algorithm>

Lower Bound

找出數列中第一個 大於或等於 target 的位置, 換句話說就是找到 >= target 的最小值的位置

// vector<int> v;
// assume v is a sorted array
auto it = lower_bound(v.begin(), v.end(), target);
int idx = it - v.begin();

Upper Bound

找出數列中第一個 大於 target 的位置, 換句話說就是找到 > target 的最小值的位置

// vector<int> v;
// assume v is a sorted array
auto it = upper_bound(v.begin(), v.end(), target) - v.begin();
int idx = it - v.begin();

lower_bound 和 upper_bound 都會回傳 對應型態的 iterator, 如果傳入的 sequence 找不到目標值,就會回傳 v.end()

  • algorithm
  • binary-search
Monday, July 24, 2023 | 1 閱讀
導覽列
  • 關於
  • 最近文章
聯絡方式:
  • jay101630@gmail.com

Toha Theme Logo Toha
Copyright © 2022 Jay’s Blog. All right reserved.
Powered by Hugo Logo