那些年，面试中常见的数据结构基础和算法题（下） (2)

扩展 如果要查找数字在数组中最后出现的位置呢？其实这跟上述算法是类似的，稍微改一下上面的算法就可以了，代码如下：

/** * 二分查找最后一次出现位置 */ int binarySearchLast(int a[], int n, int t) { int l = -1, u = n; while (l + 1 != u) { /*循环不变式, a[l] <= t < a[u]*/ int m = l + (u - l) / 2; if (t >= a[m]) l = m; else u = m; } /*assert: l+1 = u && a[l] <= t < a[u]*/ int p = l; if (p<=-1 || a[p]!=t) p = -1; return p; } 复制代码

当然还有一种方法可以将查询数字第一次出现和最后一次出现的代码写在一个程序中，只需要对原始的二分查找稍微修改即可，代码如下：

/** * 二分查找第一次和最后一次出现位置 */ int binarySearchFirstAndLast(int a[], int n, int t, int firstFlag) { int l = 0; int u = n - 1; while(l <= u) { int m = l + (u - l) / 2; if(a[m] == t) { //找到了，判断是第一次出现还是最后一次出现 if(firstFlag) { //查询第一次出现的位置 if(m != 0 && a[m-1] != t) return m; else if(m == 0) return 0; else u = m - 1; } else { //查询最后一次出现的位置 if(m != n-1 && a[m+1] != t) return m; else if(m == n-1) return n-1; else l = m + 1; } } else if(a[m] < t) l = m + 1; else u = m - 1; } <span>return</span> -1;

}
复制代码

3.旋转数组元素查找问题 题目

把一个有序数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转。现在给出旋转后的数组和一个数，旋转了多少位不知道，要求给出一个算法，算出给出的数在该数组中的下标，如果没有找到这个数，则返回 -1。要求查找次数不能超过 n。

分析

由题目可以知道，旋转后的数组虽然整体无序了，但是其前后两部分是部分有序的。由此还是可以使用二分查找来解决该问题的。

解1：两次二分查找

首先确定数组分割点，也就是说分割点两边的数组都有序。比如例子中的数组以位置2分割，前面部分{3,4,5}有序，后半部分{1,2}有序。然后对这两部分分别使用二分查找即可。代码如下：

/** * 旋转数组查找-两次二分查找 */ int binarySearchRotateTwice(int a[], int n, int t) { int p = findRotatePosition(a, n); //找到旋转位置 if (p == -1) return binarySearchFirst(a, n, t); //如果原数组有序，则直接二分查找即可 int left = binarySearchFirst(a, p+1, t); //查找左半部分 <span>if</span> (left != -1) <span>return</span> left; //左半部分找到，则直接返回 int right = binarySearchFirst(a+p+1, n-p-1, t); //左半部分没有找到，则查找右半部分 <span>if</span> (right == -1) <span>return</span> -1; <span>return</span> right+p+1; //返回位置，注意要加上p+1

}

/**

查找旋转位置
*/
int findRotatePosition(int a[], int n)
{
int i;
for (i = 0; i < n-1; i++) {
if (a[i+1] < a[i])
return i;
}
return -1;
}
复制代码

解2：一次二分查找

二分查找算法有两个关键点：1）数组有序；2）根据当前区间的中间元素与t的大小关系，确定下次二分查找在前半段区间还是后半段区间进行。

仔细分析该问题，可以发现，每次根据 l 和 u 求出 m 后，m 左边（[l, m]）和右边（[m, u]）至少一个是有序的。a[m]分别与a[l]和a[u]比较，确定哪一段是有序的。

如果左边是有序的，若 t<a[m] && t>a[l], 则 u=m-1；其他情况，l =m+1；

如果右边是有序的，若 t> a[m] && t<a[u] 则 l=m+1；其他情况，u =m-1； 代码如下：

/** * 旋转数组二分查找-一次二分查找 */ int binarySearchRotateOnce(int a[], int n, int t) { int l = 0, u = n-1; while (l <= u) { int m = l + (u-l) / 2; if (t == a[m]) return m; if (a[m] >= a[l]) { //数组左半有序 if (t >= a[l] && t < a[m]) u = m - 1; else l = m + 1; } else { //数组右半段有序 if (t > a[m] && t <= a[u]) l = m + 1; else u = m - 1; } } return -1; } 复制代码数据结构和算法面试题系列—排序算法之基础排序 0.概述