重复数字有序数组——二分查找

题目关键词：

• 有序数组；
• 重复数字；
• 返回值为从1开始计数的位置索引；

思路一

1. 使用二分查找方法，找到array[index1] ≥ target，记录index1， 然后线性递减index1，查找最早出现的满足题目要求的index0；
2. 最坏情况下，arry数组中的数字完全一样，二分查找的时间复杂度O(logN);
3. 最好情况下，index1即为题目所求位置索引，时间复杂度为O(1)；

思路二

1. 在思路一中，当找到index1之后，是否还可以继续使用二分查找呢？
2. 当然可以，继续二分查找，只要负责遍历的左右指针直接还有元素，二分查找就会一直及逆行下去；
3. 直到左右指针相等，即 left == right；
4. 此时，只需要判断array[right] >= target 是否成立；
5. 若成立，则说明当前位置即为题目所求；
6. 若不成立，则说明right已经是数组array的最右侧，找不到符合要求的元素，因此返回len(array)+1；
7. 时间复杂度：因为二分查找要完全进行到底，所以时间复杂度始终是O(logN);

以上两种思路仅为个人理解，仅供参考~