TB椰程 TypeBuddy 打字搭子

二分查找

CSP-J · 编程模板 · 代码 · cpp · 难度 4/5 · 共 386 字

有序数组中定位下标，每步砍一半

  • 查找
  • 有序数组

前置内容

正文

// ── 二分查找：升序数组找 x ──
// 每比较一次排除一半
// 复杂度 O(log n)
int lo = 0, hi = n - 1, pos = -1;
while (lo <= hi) {
    // 区间还有元素就继续找
    int mid = lo + (hi - lo) / 2;
    // 防溢出写法，别写 (lo+hi)/2
    if (a[mid] == x) {
        // 找到：记录下标，退出
        pos = mid;
        break;
    }
    // x 在右半边，扔掉左半边
    if (a[mid] < x) lo = mid + 1;
    // x 在左半边
    else hi = mid - 1;
}
// 前提：数组必须有序！
// 无序先排序再二分

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK