数据结构-查找算法

查找算法思想总结作者：昱晨日期：2016年10月15日一、算法总结1.Linearsearch：从给定表的第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功；如果到最后一个元素仍没有目标元素，则查找失败。intlinear_search(int*array,intlength,intkey){assert(array!=NULL&&length=0);for(inti=1;i=length;i++){if(array[i]==key)returni;}return0;}2.sentinelsearch如果数组长度足够，数组首位或末位为无效数据，可以设置哨兵(sentinel)，去除near_search算法中i与length的比较,避免了遍历时每次判断索引值i是否溢出。intsentinel_search(int*array,intlength,intkey){assert(array!=NULL&&length=0);array[0]=key;inti=length;while(array[i]!=key)i--;returni;}3.orderedlistsearch先对元素进行排序，在查找，排好顺序的数列可以使用二分查找进行4、binarysearch数组递增排列，从表中间开始查找目标元素。如果找到一致元素，则查找成功。如果中间元素比目标元素小，则仍用二分查找方法查找表的后半部分，反之中间元素比目标元素大，则查找表的前半部分。publicstaticintbinarySearch(Integer[]srcArray,intdes){intlow=0;inthigh=srcArray.length-1;while(low=high){intmiddle=low+((high-low)1);if(des==srcArray[middle]){returnmiddle;}elseif(dessrcArray[middle]){high=middle-1;}else{low=middle+1;}}return-1;}}二、算法比较1、顺序查找条件：无序或有序队列。原理：按顺序比较每个元素，直到找到关键字为止。时间复杂度：O(n)2、二分查找（折半查找）条件：有序数组原理：查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。时间复杂度：O(logn)3、哈希表（散列表）条件：先创建哈希表（散列表）原理：根据键值方式(Keyvalue)进行查找，通过散列函数，定位数据元素。时间复杂度：几乎是O(1)，取决于产生冲突的多少。