静态查找算法
静态查找算法：仅对查找表进行查找操作，不改变表
?
一、顺序查找
?? 算法思想：从表的一端开始，向另一端逐个按给定值kx与关键字进行比较，若找到，查找成功，并返回位置；若检测完毕，仍未找到，返回错误信息。
?
??? 算法的时间复杂度：o(n)
??? 优点：对表中数据的存储没有要求，线性链表只能进行顺序查找
??? 缺点：当n很大时，平均查找长度达，效率低。
?
package com;public class Find {public static void main(String args[]){//数组int find[] = {1,3,6,9,7,5,8};int stat = findKey(find,3);System.out.println(stat);int stat2 = findKeyR(find,78);System.out.println(stat2);}//顺序查找，从前往后，查找失败返回长度public static int findKey(int _find[], int key){int len = _find.length;int i;for(i = 0; i < len && _find[i] != key;i++);return i;}//顺序查找，从后往前，查找失败返回-1public static int findKeyR(int _find[], int key){int len = _find.length;int i;for(i = len-1; i >= 0 && _find[i] != key;i--);return i;}}?
二、折半查找（二分查找）
? ??? 折半查找是针对有序表的，即表中的数据元素按关键字升序或降序排列的表。
????? 前提要求：1.必须采用顺序存储结构?2.必须按关键字大小有序排列
????? 算法的时间复杂度：o(log(n))
????? 优点：比较次数少，查找速度快，平均性能好;
????? 缺点：要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
?
?? ?? 算法思想：
???????? 首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
package com;public class Search {public static void main(String args[]){//数组int find[] = {1,3,6,7,8,12,23};int stat = BinarySearch(find,12);System.out.println(stat);}//折半查找public static int BinarySearch(int _find[], int key){int len = _find.length;//设定返回值，失败时返回-1;int flag = -1;//区间下界int low = 0;//区间上界int high = len-1;//中间位置int mid;while(low <= high){mid = (low + high)/2;if(_find[mid] < key){low = mid + 1;}else if(_find[mid] > key){high = mid - 1;}else{flag = mid;break;}}return flag;}}?三、其他查找
?
??? 插值查找：也是针对有序表的，和二分插值的区别是，mid的取值规则
???????? mid = low+(key-array[low])*(high-low)/(array[high]-array[low])
??? 平均性能最好，只适合关键字平均分布的表 ，算法的时间复杂度：o(log(n))
?
??? 分块查找:又称索引顺序查找，是对顺序查找的改进。
????? 算法思想：将查找表分为若干个子表，每个子表分块有序，对子表建立索引表，查找表的每一个子表由索引表中的索引项确定。
??? （1）首先用给定值key在索引表中检测索引项，以确定所要进行的查找在查找表中的查找分块，索引表关键字有序，可使用折半查找；
??? （2）对该分块进行顺序查找。
?
????? 平均查找长度：索引表的平均长度和子表的平均长度的和。
???????? m个数据元素，n个子表， 平均查找长度为(m+n/m)/2+1，当m=sqrt（n）时平均长度最小。
?
?
?