查找算法

顺序查找法

时间复杂度：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)

核心思想：

1. 获取当前数组的中心下标
2. 中心值与待查数据比较，比待查数据大则将

/**
 * 查找数组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;
}

哈希查找法

查找步骤：

1. 用给定的哈希函数构造哈希表
2. 根据选择的冲突处理方法解决冲突问题
3. 在哈希表基础上执行哈希查找

哈希表建立步骤：

1. 获取元素关键字key，计算其哈希函数地址。若该地址对应的存储空间还未被占用，则将该元素存入，否则进入step2
2. 根据选择冲突的处理办法，计算key的下一个地址，直到找到存储空间为空的地址，否则继续执行step2

>>> 无符号右移(除法)，空位由0补齐