题目一(数字在排序数组中出现的次数)

统计一个数字在排序数组中出现的次数。(默认递增)

算法思路

由于数组是递增有序的，那么数字如果重复一定都在一块，那么只需查找这个数字在数组中第一次出现的位置和最后一次出现的位置。接下来只要查找位置到，然后算出两位置间的距离即得所求。

那么对于有序数组要查找位置，什么方法最快呢？毫无疑问是二分查找，因为它可以在 O(logn) 时间内快速找到查找位置。

首先对于数字 k 第一次出现进行位置查找。如果中间的数大于 k，那么该位置在数组的前半段；如果中间的数小于 k，那么该位置在数组的后半段；如果中间的数等于 k，那么如果中间的数恰好是数组的起始位置，或者中间的数的前一个数字不是 k，也就是说，已经找到了目标位置，返回即可，否则该位置出现在数组的 前半段。

同理，对于数字 k 最后一次出现进行位置查找。如果中间的数大于 k，那么该位置在数组的前半段；如果中间的数小于 k，那么该位置在数组的后半段；如果中间的数等于 k，那么如果中间的数恰好是数组的末位位置，或者中间的数的下一个数字不是 k，也就是说，已经找到了目标位置，返回即可，否则该位置出现在数组 后半段。

注意：算法要鲁棒性好，要考虑功能测试、边界值测试和特殊输入测试。例如本题功能测试为数组中包含(不包含)要查找的数字，要查找的数字在数组中出现一次或多次；边界值测试如查找数组中的最大值和最小值，数组中只有一个数字；特殊值测试如输入数组为空。

算法实现

题目二(0-n-1 中缺失的数字)
一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0-n-1 之内。在范围 0-n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

算法思路
数组递增且查找元素，依然考虑二分查找思路。
首先，如果不存在缺失值，那么数组中的每个元素和它的下标是一一对应的。那么利用二分查找，如果中间元素的值和下标相等，那么下一轮只要查找右半边(前面元素均满足下标和元素值一一对应)；如果中间的元素值和下标不相等时，如果中间的位置在首位或者它的前一个元素和前一个元素的下标相等，那么中间的数字为所求；反之，它的前一个元素和前一个元素的下标不相等，那么下一轮只要查找左半边即可。

算法实现

题目三(数组中数组和下标相等的元素)
假设一个单调递增的数组中的每个元素都是整数并且是唯一的。请编写程序实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组{-3,-1,1,3,5} 中，数字 3 和它的下标相等。

算法思路
依然使用二分查找。
如果中间的元素刚好等于中间位置，那么立即返回所求；如果中间的元素小于中间位置，那么只需在右半段查找；否则在左半段查找即可。

算法实现

复杂度
题目一：由于算法都是通过二分查找两个位置，各自所需的时间复杂度均为 O(logn)，因而总的时间复杂度还是 O(logn)。空间复杂度为 O(1)。
题目二和三的时间复杂度均为 O(logn)，空间复杂度为 O(1)。

参考
[1] <<剑指offer2>>
[2] 牛客网