网站怎么靠前/百度官方优化指南

查找

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

顺序查找（复杂度（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;
}