查找

基础知识

1.查找，常见的方法有顺序查找、二分（折半）查找、哈希表查找、二叉排序树查找。 2.二分查找代码应能信手拈来，仅适用于事先已经排好序的顺序表；哈希表和二叉排序树查找的重点在于考查对应的数据结构而不是算法，哈希表的最主要优点是我们利用它能够在O(1) 时间查找某一元素，是效率最高的查找方式，缺点是需要额外的空间实现哈希表；与二叉排序树对应的数据结构是二叉搜索树。 3.信手拈来的二分查找代码程序：

int binarySearch(const vector<int> &v, int k) { if(v.empty()) return -1; //没有找到数字k int low=0; int high=v.size()-1; int middle; while(low<=high) { middle=(high+low)/2; if(v.at(middle)==k) return middle; else if(v.at(middle) < k) low=middle+1; else high=middle-1; } return -1; //没有找到数字k }

python版：

# coding = utf-8 import sys if __name__ == "__main__": # 读取第一行的n num_to_search = int(sys.stdin.readline().strip()) input_list = list(map(int, sys.stdin.readline().strip().split())) if input_list: left=0 right=len(input_list)-1 while left<=right: mid=(left+right)//2 if input_list[mid]==num_to_search: print(mid) break elif input_list[mid]<num_to_search: left = mid+1 else: right = mid-1

4.时间复杂度：折半查找为 O(log2n) ，哈希表查找时间复杂度为 O(1) 。

应用：旋转数组的最小数字

题目 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。 思路 顺序情况下直接输出数组开头元素。旋转情况下，令index1指向开头，index2指向结尾，不断缩小数组大小，当只剩两个数字时，index2即指向最小元素。 算法实现

int BinarySearchMin(vector<int> rotationArray) { if(rotationArray.emtpy()) return -1; if(rotationArray.size() == 1) return rotationArray.at(0); int leftIndex=0; int rightIndex=rotationArray.size()-1; if(rotationArray.at(rightIndex)>rotationArray.at(leftIndex)) return rotationArray.at(0); //顺序排列 else { int midIndex=0; while(1){ if(rightIndex-leftIndex==1) return return rotationArray.at(rightIndex); midIndex=(leftIndex+rightIndex)/2; if(rotationArray.at(midIndex)==rotationArray.at(leftIndex) && rotationArray.at(midIndex)==rotationArray.at(rightIndex)) { return SequentialSearchMin(rotationArray, leftIndex, rightIndex); //遍历子空间找最小值 } if(rotationArray.at(midIndex)>=rotationArray.at(leftIndex)) leftIndex=midIndex; else rightIndex=midIndex; } } }

测试用例

vector<int> v1 = {5,6,7,8,9,1,2,3,4}; vector<int> v2 = {4,6,7,8,9,1,2,3,4}; vector<int> v3 = {1,0,1,1,1}; vector<int> v4 = {1,2,3,4,5,6,7,8,9}; vector<int> v5 = {4}; vector<int> v6 = {};

应用：数字在排序数组中出现的次数

题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。 思路 利用二分查找法分别找到第一个和最后一个3。 算法实现

int GetFirstK(const vector<int> &sortedArray, int k) { if(sortedArray.empty()) return -1; int low=0, high=sortedArray.size()-1, index=0; while(low<=high){ index=(low+high)/2; if(sortedArray.at(index)==k) { if(index==0) return index; else if(sortedArray.at(index-1)<k) return index; else if(sortedArray.at(index-1)==k) high=index-1; } else if(sortedArray.at(index)>k) high=index-1; else if(sortedArray.at(index)<k) low=index+1; } return -1; } int GetLastK(const vector<int> &sortedArray, int k) { if(sortedArray.empty()) return -1; int low=0, high=sortedArray.size()-1, index=0; while(low<=high){ index=(low+high)/2; if(sortedArray.at(index)==k) { if(index==sortedArray.size()-1) return index; else if(sortedArray.at(index+1)>k) return index; else if(sortedArray.at(index+1)==k) low=index+1; } else if(sortedArray.at(index)>k) high=index-1; else if(sortedArray.at(index)<k) low=index+1; } return -1; }

测试用例

vector<int> v1={1,2,3,3,3,4,5}; vector<int> v2={3,3,3,4,5}; vector<int> v3={1,2,3,3,3}; vector<int> v4={3}; vector<int> v5={}; cout << test(v1, 3) << endl; cout << test(v1, 4) << endl; cout << test(v1, 8) << endl; cout << test(v2, 3) << endl; cout << test(v3, 3) << endl; cout << test(v4, 3) << endl; cout << test(v5, 3) << endl;

应用：二叉搜索树与双向链表

题目： 输入一个二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。比如输入图4.12中左边的二叉搜索树，则输出转换后的排序双向链表。 思路 二叉搜索树中序遍历时即可得到从小到大的顺序排列。因此在中序遍历中每次都记住上一个遍历到的结点，然后更改指针指向即可。 注意*pLastNodeInList->m_pRight 这种写法是错误的，因为-> 比 * 优先级高。 算法实现

// BinaryTreeNode* Convert(BinaryTreeNode *pRoot) { if(pRoot==NULL) return NULL; BinaryTreeNode* pLastNodeInList=NULL; //pLastNodeInList指向双向链表的尾结点 ConvertCore(pRoot, &pLastNodeInList); BinaryTreeNode* pHeadOfList=pLastNodeInList; //找到头结点并返回 while(pHeadOfList->m_pLeft != NULL) { pHeadOfList=pHeadOfList->m_pLeft; } return pHeadOfList; } void ConvertCore(BinaryTreeNode *pNode, BinaryTreeNode** pLastNodeInList) { //此处必须用指针的指针，因为我们对*pLastNodeInList会有改变。 if (NULL == pNode) return; ConvertCore(pNode->m_pLeft, pLastNodeInList); pNode->m_pLeft=*pLastNodeInList; //程序中，令左结点指向前一个元素，右结点指向后一个元素 if(*pLastNodeInList != NULL) (*pLastNodeInList)->m_pRight=pNode; *pLastNodeInList=pNode; ConvertCore(pNode->m_pRight, pLastNodeInList); }

测试用例 无

应用：第一个只出现一次的字符

题目： 在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”，则输出'b'。 分析： 查找。我们可以统计每个字符在该字符串中出现的次数，然后根据字符来查找它出现的次数，哈希表。定义哈希表的键值(Key)是字符，而值(Value)是该字符出现的次数。扫描字符串两次完成任务。 算法实现

char FirstNotRepeatChar(char *pString) { if (!pString || !*pString) return '\0'; //空指针，或指针指向空字符 int len = strlen(pString); vector<int> charMap(256, 0); for (int i = 0; i<len; i++) { charMap[pString[i]]++; } for (int i = 0; i<len; i++) { if (charMap[pString[i]] == 1) { return pString[i]; } } return '\0'; }

测试用例

char *a= "abaccdeff"; a = NULL; a = "";