Android 面试常见 - 二分查找算法题

前言

金三银四，又是一个跳槽的季节。在面试的过程中，有时候难免会碰到一些算法题目。今天，为大家整理了二分查找常见的算法题。

主要包括以下三点

旋转数组中的最小数字

在旋转数组中查找某个数

排序数组中某个数的出现次数

旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3，4，5，1，2}为{1，2，3，4，5}的一个旋转，该数组的最小值为1.
实现数组的旋转见左旋转字符串。

解题思路

和二分查找法一样，用两个指针分别指向数组的第一个元素和最后一个元素。

我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还可以注意到最小的元素刚好是这两个子数组的分界线。我们试着用二元查找法的思路在