1. 前言
在实际编程中，我们经常会遇到查找排序数组中缺失数字的问题。如果使用内置函数，这个问题非常简单，但如果限制使用内置函数，我们该如何处理呢？本文将介绍多种不使用内置函数的方法来查找排序数组中缺失的数字。
2. 二分法
二分法是查找排序数组中某个元素的常用方法，同时也可以用来查找排序数组中的缺失数字。
2.1 算法思路
在二分法的基础上，我们可以先找出中间元素mid，然后比较mid是否等于它的下标。如果相等，则缺失的数字在mid的右侧，否则缺失的数字在mid的左侧。
2.2 代码实现
public static int FindMissingNum(int[] arr)
{
if (arr == null || arr.Length <= 0)
{
return -1;
}
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] == mid)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return left;
}
上述代码中，left和right是数组的左右边界，mid表示数组的中间位置。如果arr[mid]等于mid，说明缺失的数字在mid的右侧，我们对右半部分进行查找；否则，缺失的数字在mid的左侧，我们对左半部分进行查找。最后，left所指向的位置就是缺失的数字。
3. 递归
递归是一种常见的算法思想，也可以用来查找排序数组中的缺失数字。
3.1 算法思路
我们可以先找出数组的中间位置mid，然后比较arr[mid]是否等于mid，如果相等，则在右半部分继续查找；否则，在左半部分继续查找。递归终止的条件是左右下标相等。
3.2 代码实现
public static int FindMissingNum(int[] arr, int left, int right)
{
if (arr == null || arr.Length <= 0)
{
return -1;
}
if (left > right)
{
return left;
}
int mid = (left + right) / 2;
if (arr[mid] == mid)
{
return FindMissingNum(arr, mid + 1, right);
}
else
{
return FindMissingNum(arr, left, mid - 1);
}
}
上述代码中，left和right是数组的左右边界，mid表示数组的中间位置。如果arr[mid]等于mid，说明缺失的数字在mid的右侧，我们对右半部分进行查找；否则，缺失的数字在mid的左侧，我们对左半部分进行查找。当左右下标相等时，返回left所指向的位置，即为缺失的数字。
4. 异或
异或是一种常用的位运算符，也可以用来查找排序数组中的缺失数字。
4.1 算法思路
我们可以先将数组中的所有元素依次异或起来，然后再将1到n依次异或起来，最后将两个异或结果再次异或起来。
这个结果就是缺失的数字。
4.2 代码实现
public static int FindMissingNum(int[] arr)
{
if (arr == null || arr.Length <= 0)
{
return -1;
}
int xor1 = 0;
for (int i = 0; i < arr.Length; i++)
{
xor1 ^= arr[i];
}
int xor2 = 0;
for (int j = 1; j <= arr.Length; j++)
{
xor2 ^= j;
}
return xor1 ^ xor2;
}
上述代码中，通过两个for循环分别求出数组中所有元素和1到n的异或结果，然后将这两个结果再次异或起来，最终得到的结果就是缺失的数字。
5. 三分法
三分法是一种比二分法更加高效的查找算法，也可以用来查找排序数组中的缺失数字。
5.1 算法思路
在三分法中，我们可以先找出数组的两个中间位置mid1和mid2，然后比较arr[mid1]是否等于mid1。如果相等，则缺失的数字在mid2的左侧；否则，缺失的数字在mid1的左侧。
因为数组是排序的，所以每次查找后，我们都可以排除掉一个三分之一的区间。
5.2 代码实现
public static int FindMissingNum(int[] arr)
{
if (arr == null || arr.Length <= 0)
{
return -1;
}
int left = 0;
int right = arr.Length - 1;
while (right - left >= 2)
{
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
if (arr[mid1] == mid1)
{
left = mid2;
}
else
{
right = mid1;
}
}
return arr[left] == left ? right : left;
}
上述代码中，left和right是数组的左右边界，mid1和mid2分别表示中间位置的左右两侧。如果arr[mid1]等于mid1，说明缺失的数字在mid2的左侧；否则，缺失的数字在mid1的左侧。最后，left所指向的位置就是缺失的数字。
6. 总结
在本文中，我们介绍了多种不使用内置函数的方法来查找排序数组中的缺失数字，包括二分法、递归、异或和三分法。虽然这些算法没有内置函数来的简单，但是它们的思想和实现方法可以提高我们的编程能力和解决问题的能力。