1.1 Basic Programming Model：从表达式到二分查找

1.1 · Basic Programming Model覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“1.1 · Basic Programming Model”如何把 Java 表达式、数组、静态方法、API、输入输出与二分查找连成可执行程序合同
能逐项核对基础编程模型、原始数据类型与表达式、数组与静态方法、API与字符串、输入与输出、二分查找，并区分作者站内容与本页独立补充
能按“remaining = hi - lo + 1；下一轮 remaining ≤ floor(上一轮 remaining / 2)”手算一个最小输入，逐步检查“若 key 存在，它始终位于闭区间 a[lo..hi]；区间为空时才能报告未找到”
能注入“不验证数组已有序，或用可能溢出的 (lo + hi) / 2 计算中点”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“1·1 · Basic Programming Model”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“1·1 · Basic Programming Model”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“1·1 · Basic Programming Model”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：1.1 · Basic Programming Model

1. 基础编程模型：在本页通过“解析输入类型”连接解释、交互状态和练习验收。
2. 原始数据类型与表达式：在本页通过“验证数组有序”连接解释、交互状态和练习验收。
3. 数组与静态方法：在本页通过“计算安全中点”连接解释、交互状态和练习验收。
4. API与字符串：在本页通过“收缩候选区间”连接解释、交互状态和练习验收。
5. 输入与输出：在本页通过“返回索引证书”连接解释、交互状态和练习验收。
6. 二分查找：在本页通过“解析输入类型”连接解释、交互状态和练习验收。

从“代码能运行，不等于模型已说清”开始

基础编程模型（basic programming model）不是Java语法速查表。它给后续全书建立共同实验语言：algorithm要写成完整program，input要能重放，output要能比较，数据结构要通过API隔离，性能判断要建立在明确operations之上。

先预测 7 / 2 与 7 / 2.0 是否都得到 3.5。不会：前者两个operands都是 int，执行integer division得到 3；后者提升为 double 才得到 3.5。如果连expression type都未确认，binary search里的index arithmetic、random simulation里的probability和analysis里的measurements都会从第一步偏离。

官方1.1依次覆盖 Primitive data types and expressions、Statements、Arrays、Static methods、APIs、Strings、Input and output、Binary search，并给出标准输入输出、drawing、audio与image processing libraries。这里不把这些主题压成“会写Java”一句话，而是把每一层的contract接到可验证程序上。

1.1.1 原始数据类型、表达式与语句

原始数据类型与表达式（primitive data types and expressions）从四类常用types开始：int 表示整数，double 表示浮点数，boolean 表示逻辑值，char 表示单个字符。Expression不是只看符号；operand types决定operator的含义、promotion与result type。

int quotient = 7 / 2;          // 3
double ratio = 7 / 2.0;       // 3.5
boolean safe = n > 0 && total / n > limit;
char first = name.charAt(0);

&& 与 || 是short-circuit operators。上例在 n <= 0 时不会计算右侧，因此避免division by zero；若改成bitwise &，两个operands都会求值。Cast也不是精度恢复工具：(double) (7 / 2) 先完成integer division，再把 3 转成 3.0；必须在除法前转换operand。

Statement把expressions组织成state transitions。Assignment改变variable绑定或object content，conditional在branches间选择，loop重复执行block，method call转移控制并返回。可靠阅读方式是为每个block写出进入前state、guard和退出后state，而不是只追某次sample output。

1.1.2 数组：连续索引与reference语义

数组与静态方法（arrays and static methods）是本节把数据和algorithm连接起来的核心。Java array是固定长度、同一element type、由0开始索引的object；a.length 是field，不是method。有效区间是 0 到 a.length - 1，empty array的最后index是 -1，因此基于length写loop比硬编码边界可靠。

数组别名来自assignment只复制reference：

int[] a = { 2, 4, 6, 8 };
int[] b = a;
b[1] = 99;              // a[1] is also 99
 
int[] c = a.clone();
c[1] = -1;              // a is unchanged

二维数组在Java中是array of arrays，各rows可以有不同length。算法若假设rectangular matrix，必须验证每一行；只检查 a.length 不能证明 a[i][j] 有效。复制也分层：outer array的 clone 只复制row references，真正deep copy要逐row复制。

1.1.3 静态方法：把算法变成带契约的operation

静态方法让algorithm拥有可复用name、parameters与return value。Java永远pass by value：primitive parameter得到value copy，array parameter得到reference value的copy。Method可以改动所指array elements，却不能通过重新赋值parameter改变caller variable指向。

public static int gcd(int p, int q) {
    if (q == 0) return p;
    return gcd(q, p % q);
}

Euclid method的termination argument不是“看起来会停”：当 q 为正时，p % q 落在0到 q - 1，第二parameter严格下降，最终到0。每次recursive call拥有独立parameter values；return时按相反顺序回到caller。对于可能为负的inputs还要先规定normalization，否则 % 的sign semantics会让契约含糊。

Method overloading根据compile-time argument types选择signature，不能只靠return type区分。Side effects也应进入API说明：pure method只由arguments决定result，更容易测试；mutating method必须说明修改哪个object、是否保留ordering以及异常时state是否完整。

1.1.4 API与字符串：client只依赖公开契约

API与字符串（APIs and strings）把program拆成client与implementation。API不仅是method列表，还包括preconditions、postconditions、side effects和failure behavior。后续章节每个data type都先给API，再比较多种implementation。

String 是immutable object。Concatenation产生新string；length()、charAt()、substring()提供query。内容相等要用 equals，因为 == 比较两个variables是否持有同一object reference：

String a = new String("key");
String b = new String("key");
 
boolean sameReference = (a == b);  // false
boolean sameContent = a.equals(b); // true

Immutable value使string可以安全作为symbol-table key，但大量loop内concatenation可能反复创建objects；性能敏感构建应使用appropriate buffer。String indexing以UTF-16 code units为基础，不等于所有Unicode user-perceived characters；本书ASCII-oriented examples成立时，也要明确alphabet assumption。

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“1.1 · Basic Programming Model”的两个最小情境间切换，再逐项选择正式概念。预测“remaining = hi - lo + 1；下一轮 remaining ≤ floor(上一轮 remaining / 2)”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

1.1 · Basic Programming Model：对象、操作与不变量

把 Java 表达式、数组、静态方法、API、输入输出与二分查找连成可执行程序合同

选择最小情境

切换正式概念

表达式边界: 比较 7 / 2、7 / 2.0 与 (double) (7 / 2)
当前观察: basic programming model：先由操作数类型决定除法语义，再谈结果值

remaining = hi - lo + 1；下一轮 remaining ≤ floor(上一轮 remaining / 2)

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

基础编程模型：在实验 1 中指出对应状态，并写出一个通过条件。
原始数据类型与表达式：在实验 2 中指出对应状态，并写出一个通过条件。
数组与静态方法：在实验 3 中指出对应状态，并写出一个通过条件。
API与字符串：在实验 1 中指出对应状态，并写出一个通过条件。
输入与输出：在实验 2 中指出对应状态，并写出一个通过条件。
二分查找：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“remaining = hi - lo + 1；下一轮 remaining ≤ floor(上一轮 remaining / 2)”不是孤立结论？

问题 3：故障恢复。 怎样证明“不验证数组已有序，或用可能溢出的 (lo + hi) / 2 计算中点”已经修复？

保存输入类型、数组快照、lo/mid/hi、比较结果、退出原因与线性扫描预言机作为正常基线；注入该故障并标记第一个违反“若 key 存在，它始终位于闭区间 a[lo..hi]；区间为空时才能报告未找到”的状态；撤销后用完全相同的输入、版本和随机种子重放。只有全部状态与独立预言机重新一致，才可发布修复结论。

本章回顾

Basic programming model把primitive expressions、statements、arrays、methods、APIs与I/O统一成后续算法实验语言。
Expression semantics由types决定；integer division、promotion与short-circuit都必须先于数值直觉。
Array是reference object，assignment会alias，valid indices永远止于 length - 1。
Static method接收value copies；algorithm contract还必须说明termination与side effects。
API隔离client与implementation，String内容比较使用 equals。
Standard input/output让dataset可重放、output可比较，media libraries也应保留deterministic evidence。
Binary search依赖sorted precondition与closed-interval invariant，返回某个match不等于rank。