2个线性表查找的优化
原创
1.无序表的查找优化
问题：在一个无序的数组中查找是否存在目标值target；
解法一：
这恐怕是最为直接，最容易想到的解法了！
public boolean squenceSearch(int [] arr,int target){
if (arr == null || arr.length == 0) return false;
for (int i= 0 ; i< arr.length;i++){
if (arr[i] == target) return true;
}
return false;
}解法二：
设置arr[0]为target,称之为哨兵。
public int squenceSearchII(int [] arr,int target){
if (arr == null || arr.length == 0) return -1;
if (arr[0] == target) return 0;
int temp = arr[0];
arr[0] = target;
int i = arr.length-1;
while (arr[i] != target) {
i--;
}
arr[0] = temp;
return i == 0 ? -1:i;
}解法一，执行一次for循环需要两次判断，解法二只需要一次判断。
2.有序表的二分查找法的优化
在二分查找中，我们常常对mid的更新为：
mid = left +(right - left)/2;你是否想过，为是1/2而不是1/4或1/3呢？
实际上，如果待查的数据比较均匀，那么1/2是一个很好的选择，一旦待查数据中的数据是极度不均匀的，那么就需要考虑插值查找法。
我们将1/2用 (target - arr[left])/(arr[right] - arr[left])代替，就是插值查找法。于是mid的更新变为：
mid = left +(target - arr[left])/(arr[right]- arr[left])*(right - left);原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录