如果面试题要求在排序的数组（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数，都可以尝试用二分查找算法。如果需要在O(1)时间内查找某一元素，则考虑哈希表结构，其缺点是需要额外的空间来实现。
- 旋转数组的最小数字（二分查找）
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1.
分析：普通查找遍历一遍数组就能找到最小元素，复杂度O(1)，显然不行。旋转数组在一定程度上是排序的，试使用二分查找法来解决。同二叉查找算法设置两个指针分别指向头尾，那么可以知道，第一个指针总是指向前面递增数组的元素，第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后一个元素，而第二个指针会指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素，这就是循环结束的条件。特别注意两指针与两指针中间的数字都相等的情况，需采用顺序查找来判断中间的数组是属于前子数组还是后子数组。
//顺序查找 int MinInOrder(int* numbers,int index1,int index2) { int result = numbers[index1]; for(int i=index1+1;i<=index2;++i) { if(result > numbers[i]) result = numbers[i]; } return result; } int Min(int* numbers,int length) { if(numbers == NULL || length <=0) return NULL; int index1 = 0; int index2 = length-1; int indexMid = index1; while(numbers[index1]>=numbers[index2]) { if(index2 - index1 == 1) { //最后终止条件 indexMid = index2; break; } indexMid = (index1+index2)/2; //顺序查找条件 if(numbers[index1] == numbers[index2] && numbers[index1] == numbers[indexMid]) return MinInOrder(numbers,index1,index2); //最小数在右子数组 if(numbers[indexMid] >= numbers[index1]) index1 = indexMid; //最小数在左子数组 else if(numbers[indexMid] <= numbers[index2]) index2 = indexMid; } return numbers[indexMid];//如果旋转了0个数字，即第一个数就为最小数 } - 题1的延伸：在该旋转数组中查找某个数
题目：Given a sorted array of n integers that has been rotated an unknown number of times,given an O(logn) algorithm that finds an element in the array.You may assume that the array was originally sorted in increasing order.
e.g. Find 5 in array(15,16,19,20,25,1,3,4,5,7,10,14)
Output:8(index of 5 in the array)int search(int *a,int begin,int end,int val) { while(begin<=end) { int middle = (begin+end)/2; if(val == a[middle]) return middle; //begin---middle区间单调增长 else if(a[begin]<=a[middle]) { if(val>a[middle]) begin=middle+1; else if(val>=a[begin]) end=middle-1; else begin=middle+1;//<a[begin]在后半段 } //19,20,25,1,3,4,5 val=3 a[middle]=5 else if(val < a[middle]) end=middle-1; //20,25,1,3,4,5 val= 3 a[middle]=1 a[end]=5 else if(val <= a[end]) begin=middle+1; //>a[end] 在前半段 else end=middle-1; } return -1; }p.s.如果有重复元素，只可以使用线性搜索。
- 数字在排序数组中出现的次数（二分查找）
题目：统计一个数字k在排序数组中出现的次数。例如{1,2,3,3,3,3,4,5}和3，输出4.
分析：就是要确定第一个k和最后一个k的位置。用二分查找法总是比较数组中间的数字和k，若中间数字比k大，k只会出现在前半段，反之后半段。若中间数字和k相等了，判断前一个数字是不是k，若不是该数就是第一个k，若是，则第一个k在数组的前半段，继续查找。时间复杂度O(logn)。
int GetFirst(int* data,int len,int k,int begin,int end) { if(begin > end) return -1; int mid = (begin+end)/2; int midData = data[mid]; if(midData == k) { if((mid > 0 && data[mid-1]!=k )|| mid == 0)//mid=0 return mid; else end = mid-1; } else if(mid > k) end = mid-1; else begin = mid+1; return GetFirst(data,len,k,begin,end); } int GetLast(int* data,int len,int k,int begin,int end) { if(begin > end) return -1; int mid = (begin+end)/2; int midData = data[mid]; if(midData == k) { if((mid < len-1 && data[mid+1]!=k )|| mid == len-1) return mid; else begin = mid+1; } else if(mid < k) begin = mid+1; else end = mid-1; return GetLast(data,len,k,begin,end); } int number(int* data,int len,int k) { int number = 0; if(data != NULL && len > 0) { int first = GetFirst(data,len,k,0,len-1); int last = GetLast(data,len,k,0,len-1); if(first > -1 && last > -1) number = last-first+1; } return number; } - 第一个只出现一次的字符（哈希表特性）
题目：在字符串中找出第一个只出现一次的字符。例如“abaccdeff”，输出b。
分析：哈希表，第一次扫描字符串，每扫描到一个字符就在哈希表对应项上次数加一，第二次扫描，直接从哈希表中获取字符出现的次数，这样第一个只出现一次的字符就是。使用char数组来实现哈希，char共8位，256种可能，创建长度为256的数组，根据字母的ASCII码作为数组下标对应数组的一个数字，而数组中存储的就是每个字符出现的次数。
延伸：1.输入两个字符串，从第一个字符串中删除第二个字符串中出现过的所有字符。创建一个用数组实现的简单哈希表来存储第二个字符串，再扫描第一个字符串时，用O(1)的时间判断出该字符是否在第二个字符中。2.删除字符串中所有重复出现的字符。布尔型数组实现哈希。3.变位词。都是用很小的空间消耗换取时间效率。char NotReapting(char *pString) { if(pString == NULL) return '\0'; const int size = 256; unsigned int hashTable[size]; for(int i = 0;i < size; ++i) hashTable[i] = 0; char *cur = pString; while(*cur != '\0') hashTable[*(cur++)]++; cur = pString; while(*cur != '\0') { if(hashTable[*cur] == 1) return *cur; cur++; } return '\0'; } - 数组中出现次数超过一半的数字(快速排序中的Partition)
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数组。例如{1,2,3,2,2,2,5,4,2}长度9,2出现了5次，因此输出2.
解法一：基于Partition函数的O(n)算法
分析：数组中有个数字出现次数超过了数组长度的一半，如果这个数组排序，那么排序之后位于中间的数字就是那个出现次数超过长度一半的数字，即中位数。使用快速排序的Partition函数。（会修改数组）
int MoreThanHalf(int *num,int len) { int middle = len/2; int begin = 0; int end = len-1; //数组中随机选择一个数字，然后调整数组中的数字的顺序 //最后找到中位数 int index = Partition(num,len,begin,end); while(index != middle) { if(index > middle) { end = index - 1; index = Partition(num,len,begin,end); } else { begin = index + 1; index = Partition(num,len,begin,end); } } int result = num[middle]; return result; }解法二：根据数组特点找出的O(n)算法
分析：遍历数组的时候保存两个值，一个是数字，一个是次数，如果这个数字和之前保存的数字相同，次数+1，如果不同，次数-1，当次数为0时，保存下一个数并把次数设1.由于要找的数字肯定比其他所有数字出现的次数之和还要多，所以要找的数字肯定是最后一次把次数设为1的数字。
int MoreThanHalf2(int* numbers,int len) { int result = numbers[0]; int count = 1; for(int i = 1;i < len; ++i) { if(count == 0) { result = numbers[i]; count = 1; } else if(numbers[i] == result) count += 1; else count -= 1; } return result; } - 题目：已知两个已排序数组A和B，A有足够的空间。试写一个函数使的A和Bmerge并排好序。
分析：标准merge-sort的一部分，从后往前。void merge(int* a,int* b,int alen,int blen) { int last = alen+blen-1; int i = alen-1; int j = blen-1; while(i>=0&&j>=0) { if(a[i]>b[j]) a[last--]=a[i--]; else a[last--]=b[j--]; } //no need to copy a after running out of b's //already in place while(j>=0) a[last--]=b[j--]; } - Write a method to sort an array of strings so that all the anagrams are next to each other.
分析：先将string按字母排序，再排序string数组。 - If you have a 2GB file with one string per line,which sorting algorithm would you use to sort the file and why?
(means do not want you to bring all the data into memory)
Let’s assume we have x MB of memory available.
1) Divide the file into K chunks,where x*K=2GB.Bring each chunk into memory and sort the lines as usual using any O(nlogn) algorithm.Save the lines back to the file.
2) Now bring the next chunk into memory and sort.
3) Once we’re done,merge them one by one.(N-way merge) - Given a sorted array of strings which is interspersed with empty strings,write a method to find the location of a given string.
e.g.find “ball” in [“at”,””,””,””,”ball”,””,””,”car”,””,””,”dad”,””,””]will return 4. find “ballcar” will return -1.
分析：仍使用二分查找，不同的是如果遇到空的字符串，需要查找到下一个非空字符串为止，如果查找不到非空字符串，继续查找左半段。int search(string* strArr,string str,int begin,int end) { while(begin<=end) { //保证end指向非空字符串 while(begin<=end&&strArr[end]=="") { --end; } if(end<begin) return -1;//空字符串数组 int mid = (begin+end)/2; while(strArr[mid]=="") { ++mid;//查找后面第一个非空字符串 } if(strArr[mid]==str) return mid; else if(strArr[mid]<str) begin=mid+1; else end=mid-1; } return -1; } - 题目：已知一个矩阵，每一行都有序(从左到右递增)，且每一列也有序(从上到下递增)，在该矩阵中查找某个数。
分析：淘汰法。从最后一列第一个元素开始判断，每次可以淘汰一整列。bool FindElem(int** matrix,int val,int M,int N) { int row=0; int col=N-1; while(row<M && col>=0) { if(matrix[row][col]==val) return true; else if(matrix[row][col]>val) col--; else row++; } return false; }