当前位置：首页 > java >正文

嵌入式面试常见算法题解析：数组元素移动与二分查找

java 2025/7/18 8:40:31

一、数组后 100 个元素移到前面

1. 需求分析

已知 int 数组a[1000]，需要将数组的后 100 个数据移动到前面，前面的数据依次后退。例如，若数组初始存入的数据是 1、2、3……1000，移动后的数据结果是 901、902……1000、1、2……900。这要求在操作数组时，合理规划数据的临时存储与移动，避免数据丢失或覆盖错误。

2. 实现思路（临时数组法）

临时数组暂存：创建临时数组，先将原数组后 100 个元素复制进去，防止移动前面元素时这些数据丢失。
原数组元素后移：将原数组前 900 个元素从后往前移动 100 位，避免覆盖未移动元素。
还原临时数组：将临时数组中的后 100 个元素放回原数组前部。

3. 代码实现（临时数组法）

#include <stdio.h>void moveArray(int a[1000]) {int temp[100]; // 临时数组，存储原数组后 100 个元素// 步骤一：复制后 100 个元素到临时数组for (int i = 0; i < 100; i++) {temp[i] = a[900 + i]; // 后 100 个元素起始下标为 900（数组下标从 0 开始）}// 步骤二：前 900 个元素后移 100 位（从后往前移）for (int j = 899; j >= 0; j--) {a[j + 100] = a[j]; // 避免覆盖未移动元素}// 步骤三：将临时数组元素放回数组前部for (int k = 0; k < 100; k++) {a[k] = temp[k]; // 还原后 100 个元素到数组前面}
}int main() {int a[1000];// 初始化数组 a 为 1 到 1000for (int i = 0; i < 1000; i++) {a[i] = i + 1;}moveArray(a);// 验证输出前 200 个元素for (int i = 0; i < 200; i++) {printf("%d ", a[i]);}return 0;
}

4. 易错点

数组下标计算错误：后 100 个元素起始下标是 900，若写成 100 会越界，导致数据错误。
元素后移方向错误：必须从后往前移（如 j 从 899 开始），若从前往后移，会覆盖未移动元素，丢失数据。

5. 拓展：三次反转法（更优解）

无需临时数组，节省空间，适合大数据量。

第一次反转：反转前 900 个元素（下标 0 到 899）。
第二次反转：反转后 100 个元素（下标 900 到 999）。
第三次反转：整体反转整个数组（下标 0 到 999）。

代码实现：

#include <stdio.h>// 反转函数：反转数组从 start 到 end 的部分
void reverse(int arr[], int start, int end) {while (start < end) {int temp = arr[start];arr[start] = arr[end];arr[end] = temp;start++;end--;}
}void moveArrayBetter(int a[1000]) {// 第一次反转：前 900 个元素reverse(a, 0, 899);// 第二次反转：后 100 个元素reverse(a, 900, 999);// 第三次反转：整个数组reverse(a, 0, 999);
}int main() {int a[1000];for (int i = 0; i < 1000; i++) {a[i] = i + 1;}moveArrayBetter(a);for (int i = 0; i < 200; i++) {printf("%d ", a[i]);}return 0;
}

反转函数解释：

arr 是操作的数组，start 是起始下标，end 是结束下标。
通过循环交换 start 和 end 下标的元素，start 自增，end 自减，直至 start >= end，完成反转。

通过临时数组法和三次反转法的学习，能深入理解数组操作的逻辑，掌握不同场景下的优化思路，避免常见错误，为嵌入式面试中的算法题做好充分准备。

二、二分查找算法

1. 需求分析

二分查找（Binary Search），又称折半查找，用于在有序数组中查找目标值。若找到，返回其下标；若未找到，返回 -1。它是一种高效的查找算法，时间复杂度为 O(logN)，比顺序查找的 O(N) 效率高很多，适用于大数据量的有序数组查找。

2. 实现思路

初始化指针：定义左指针 left 指向数组起始位置（下标 0），右指针 right 指向数组末尾位置（下标 size - 1）。
循环查找：在 left <= right 的条件下，计算中间位置 mid。比较目标值 target 与 arr[mid]：
- 若相等，返回 mid（找到目标）。
- 若 arr[mid] < target，说明目标在右半区，调整 left = mid + 1。
- 若 arr[mid] > target，说明目标在左半区，调整 right = mid - 1。
终止条件：若循环结束仍未找到（left > right），返回 -1。

3. 代码实现

#include <stdio.h>int binarySearch(int arr[], int target, int size) {int left = 0;          // 左指针，指向数组起始位置int right = size - 1;  // 右指针，指向数组末尾位置while (left <= right) {  // 循环条件：左指针 <= 右指针，确保还有元素可查int mid = left + (right - left) / 2;  // 计算中间位置，防止 (left + right) 溢出if (arr[mid] == target) {return mid;  // 找到目标，返回下标} else if (arr[mid] < target) {left = mid + 1;  // 目标在右半区，左指针右移} else {right = mid - 1;  // 目标在左半区，右指针左移}}return -1;  // 未找到目标，返回 -1
}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13};int target = 7;int size = sizeof(arr) / sizeof(arr[0]);  // 计算数组元素个数int index = binarySearch(arr, target, size);  // 调用二分查找if (index != -1) {printf("找到目标，下标为：%d\n", index);} else {printf("未找到目标\n");}return 0;
}

4. 易错点

循环条件错误：必须是 left <= right。若写成 left < right，会漏掉最后一个元素的检查。例如，当数组只剩一个元素时，left == right，若条件为 <，循环不执行，直接返回 -1，导致漏判。
数组无序：二分查找的前提是数组有序。若输入的数组未排序，需先排序（如冒泡排序、快速排序等），否则算法失效。
下标越界与溢出：计算 mid 时，(left + right) / 2 可能因 left + right 超过整数范围导致溢出。使用 left + (right - left) / 2 可避免此问题，既保证计算正确，又不影响逻辑。

5. 拓展

查找第一个匹配元素：若数组中有多个相同元素，要找第一个出现的。只需在 arr[mid] == target 时，继续在左半区查找，更新 right = mid - 1，并记录当前下标。
代码示例（在原 binarySearch 基础上修改）：

int binarySearchFirst(int arr[], int target, int size) {int left = 0, right = size - 1, result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {result = mid;  // 记录当前下标right = mid - 1;  // 继续在左半区找更前的匹配} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return result;
}

查找最后一个匹配元素：类似地，在 arr[mid] == target 时，继续在右半区查找，更新 left = mid + 1，记录当前下标。
代码示例：

int binarySearchLast(int arr[], int target, int size) {int left = 0, right = size - 1, result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {result = mid;  // 记录当前下标left = mid + 1;  // 继续在右半区找更后的匹配} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return result;
}