大话数据结构011 顺序查找与有序查找

查找

 

根据给定的值，查询指定的数据。

 

顺序查找（复杂度（O(N)））

 

从线性表的第一个元素开始查找，能够和给定的值进行匹配的时候，就可以返回这个数据，直到最后一个元素。如果所有元素都不匹配的话，就是找不到。

int Search(int[] arr, int target) { if(arr == null || arr.length <= 0) { return -1; } for(int i =0; i < arr.length; i++) { if(arr[i] == target) return i; } return -1; }

顺序查找优化算法（复杂度（O(N)））

 

 

将第一个元素设置为哨兵，如果最后查找到第一个元素才是要查找的元素时，说明线性表中不存在该值。(数组元素从小标1开始存储，空出小标0的位置作为哨兵)

int Search(int[] arr, int target) { if(arr == null || arr.length <= 0) { return -1; } arr[0] = target; int i = arr.length-1; while(arr[i]!=target) { i--; } return i; }

从最大的下标开始，依次递减，直至值与目标一致停止。

 

折半查找法（复杂度（O(LogN)））

 

对于有顺序的线性表，从小到大进行排序后，先找到线性表的中间，如果查找成功则返回，如果这个值比要查找的值大，在左半部分继续查找，否则，在右半部分继续查找。

int Search(int[] arr, int target) { int low = 0; int high = arr.length -1; int mid = 0; while(low<=high) { mid = (low+high)/2; if(target < arr[mid]) { high = mid -1; }else if(target > arr[mid]){ low = mid + 1; }else{ return mid; } } return -1; }

更新指针位置：

插值查找（复杂度（O(LogN)））

 

对于分布比较均匀的线性表可以采用插值查找法：

将折半的更新次序：

mid = (low+high)/2;

变式是： 

变更为：

mid = low + (heigh -low)*(target - arr[low]) / (arr[high] - arr[low]);

 

斐波那契查找（复杂度（O(LogN)））

 

根据斐波那契数列进行查找：

 

int Search(int[] arr, int target) { int low = 0; int high = arr.length -1; int mid; int i = 0,k = 0; //找到n处于斐波那契的位置 while(arr.length > F[k]-1) { k++; } //将后面的元素进行补全 for(i = arr.length;i < F[k] -1; i++) { a[i] = a[n]; } while(low<=high) { mid = low + F[k-1] -1; if(target<arr[mid]) { high = mid - 1; k= k-1; }else if(target>arr[mid]) { low = mid + 1; k = k-2; }else{ if(mid<=n){ return mid; } else{ return arr.length -1; } } } return -1; }