[经典面试题]二分查找问题汇总

给定一个有序（非降序）数组a，可含有重复元素，求最小的i使得a[i]等于target，不存在则返回-1。

此题也就是求target在数组中第一次出现的位置。这里可能会有人想先直接用原始的二分查找，如果不存在直接返回-1，

如果存在，然后再顺序找到这个等于target值区间的最左位置，这样的话，最坏情况下的复杂度就是o（n）了，没有完全发挥出二分查找的优势。

这里的解法具体过程请参考实现代码与注释。

给定一个有序（非降序）数组a，可含有重复元素，求最大的i使得a[i]等于target，不存在则返回-1

和上题类似

给定一个有序（非降序）数组a，可含有重复元素，小于target的最大元素的位置，不存在则返回-1

这个问题可以转换为给定一个有序（非降序）数组a，可含有重复元素，等于target的最小元素的前一个，不存在则返回-1

给定一个有序（非降序）数组a，可含有重复元素，大于target的最小元素的位置，不存在则返回-1

这个问题可以转换为给定一个有序（非降序）数组a，可含有重复元素，等于target的最大元素的后一位置，不存在则返回-1

给定一个有序（非降序）数组a，可含有重复元素，求target在数组中出现的次数

上面已经求出给定一个有序（非降序）数组a，可含有重复元素，求等于target最小位置和最大位置。

给定一个有序（非降序）数组a，可含有重复元素，求target在数组中出现的下标范围

具体参考：[leetcode]34.search for a range

给定一个有序（非降序）数组a，可含有重复元素，求target在数组中下标位置，如果找不到，则返回插入位置。

具体参考：[leetcode]35.search insert position

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

具体参考：[经典面试题]输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。

具体参考：[leetcode]33.search in rotated sorted array

[leetcode]153.find minimum in rotated sorted array

[leetcode]154.find minimum in rotated sorted array ii