查找算法
顺序查找法
时间复杂度：O(n)
public void int linearSearh(int[] a,int num){
if(data==null||a.length<1)return -1;
for (int i=0;i<a.length;i++)
if(a[i]==num)
return i;
return -1;
}
二分法查找
二分法查找适用于有顺序的序列
时间复杂度：O(n)
核心思想：
- 获取当前数组的中心下标
- 中心值与待查数据比较，比待查数据大则将
/**
* 查找数组a中是否有num，有则返回下标
*/
public int binarySearch(int[] arr,int target){
int l = 0, r = arr.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == target) {
return mid;
} else if (target < arr[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1;
}
哈希查找法
查找步骤：
- 用给定的哈希函数构造哈希表
- 根据选择的冲突处理方法解决冲突问题
- 在哈希表基础上执行哈希查找
哈希表建立步骤：
- 获取元素关键字key，计算其哈希函数地址。若该地址对应的存储空间还未被占用，则将该元素存入，否则进入step2
- 根据选择冲突的处理办法，计算key的下一个地址，直到找到存储空间为空的地址，否则继续执行step2
>>> 无符号右移(除法)，空位由0补齐
