一、顺序查找

顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。

基本思路   从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。 复杂度分析　   查找成功时的平均查找长度为： ASL = 每个元素被查找的概率 * 总的元素的个数=1/n*(1+2+3+…+n) = (n+1)/2 ;   当查找不成功时，需要n+1次比较，时间复杂度为O(n)，所以，顺序查找的时间复杂度为O(n)。 优缺点   缺点：是当n 很大时，平均查找长度较大，效率低；   优点：是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。

  public static int sequentialSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i;
            }
        }
        return -1;
    }

二、二分查找

迭代法示例代码如下

	static  int binarySearch1(int arr[],int len,int target){
		/*初始化左右搜索边界*/
	    int left=0,right=len-1;
	    int mid;
	    while(left<=right){
	    	/*中间位置：两边界元素之和/2向下取整*/
	        mid=(left+right)/2;
	        /*arr[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
	        if(target<arr[mid]){
	            right=mid-1;
	        /*arr[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
            }else if(target>arr[mid]){
	            left=mid+1;
	        /*搜索到对应元素*/
	        }else if(target==arr[mid]){
	            return mid;
	        }
	    }
	    /*搜索不到返回-1*/
	    return -1;
	}

递归法示例代码如下：

	static int binarySearch2(int array[],int left,int right,int target){
		if(left<=right){
			int mid=(left+right)/2;
			/*搜索到对应元素*/
			if(array[mid]==target){
				return mid;
			}else if(array[mid]<target){
				/*array[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
				return binarySearch2(array,mid+1,right,target);
			}else{
				/*array[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
				return binarySearch2(array,left,mid-1,target);
			}
		}else{
			return -1;
		}
	}

三、插值查找

迭代法插值查找示例代码如下：

	private static int insertSearch1(int arr[],int target){
		/*初始化左右搜索边界*/
	    int left=0,right=arr.length-1;
	    int mid;
	    while(left<=right){
	        mid=left+(target-arr[left])/(arr[right]-arr[left])*(right-left);
	        /*arr[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
	        if(target<arr[mid]){
	            right=mid-1;
	        /*arr[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
            }else if(target>arr[mid]){
	            left=mid+1;
	        /*搜索到对应元素*/
	        }else if(target==arr[mid]){
	            return mid;
	        }
	    }
	    /*搜索不到返回-1*/
	    return -1;
	}

递归法插值查找示例代码如下：

	private static int insertSearch2(int array[],int left,int right,int target){
		if(left<=right){
			int mid=left+(target-array[left])/(array[right]-array[left])*(right-left);
			/*搜索到对应元素*/
			if(array[mid]==target){
				return mid;
			}else if(array[mid]<target){
				/*array[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
				return insertSearch2(array,mid+1,right,target);
			}else{
				/*array[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
				return insertSearch2(array,left,mid-1,target);
			}
		}else{
			return -1;
		}
	}

四、斐波那契查找

public class FibonacciSearch {
	
	public static int FLENGTH = 20;
	public static void main(String[] args) {
		int [] arr = {1,8,10,89,100,134};
		int target = 89;
		System.out.println("目标元素在数组中位置是：" + fibSearch(arr, target));		
	}

	public static int[] fib() {
		int[] f = new int[FLENGTH];
		f[0] = 1;
		f[1] = 1;
		for (int i = 2; i < FLENGTH; i++) {
			f[i] = f[i-1] + f[i-2];
		}
		return f;
	}
	
	public static int fibSearch(int[] arr, int target) {
		int low = 0;
		int high = arr.length - 1;
		int k = 0; 
		int mid = 0; 
		int f[] = fib();
		/*获取最相邻的斐波那契数组中元素的值，该值略大于数组的长度*/
		while(high > f[k] - 1) {
			k++;
		}
		/*因为 f[k]值可能大于arr的长度。如果大于时，需要构造一个新的数组temp[]，将arr数组中的元素拷贝过去，不足的部分会使用0填充*/
		int[] temp=Arrays.copyOf(arr, f[k]);
		/*然后将temp后面填充的0，替换为最后一位数字
		 *如将temp数组由{1,8,10,89,100,134,0,0}变换为{1,8,10,89,100,134,134,134}*/
		for(int i = high + 1; i < temp.length; i++) {
			temp[i] = arr[high];
		}
		
		while (low <= high) { 
			mid = low + f[k - 1] - 1;
			if(target < temp[mid]) { 
				high = mid - 1;
				/*因为f[k]=f[k-1]+f[k-2]，所以k--就相当于取temp数组的左边部分*/
				k--;
			} else if ( target > temp[mid]) { 
				low = mid + 1;
				/*同理，f[k]=f[k-1]+f[k-2]，k -= 2就相当于取temp数组的右边部分*/
				k -= 2;
			} else {
				/*原arr数组中的值*/
				if(mid <= high){
					return mid;
				/*在temp中，扩展出来的高位的值*/
				}else{
					return high;
				}
			}
		}
		return -1;
	}
}

五、树表查找

public class BinarySortTree {
    
    public static void main(String[] args) {
        int[] array = {35,76,6,22,16,49,49,98,46,9,40};
        BinaryTree root = new BinaryTree(array[0]);
        for(int i = 1; i < array.length; i++){
            createBST(root, array[i]);
        }
        System.out.println("中序遍历结果：");
        midOrderPrint(root);
        System.out.println();
        searchBST(root, 22, null);
        searchBST(root, 100, null);
    }
    
    /*创建二叉排序树*/
    public static void createBST(BinaryTree root, int element){
        BinaryTree newNode = new BinaryTree(element);
        if(element > root.value){
            if(root.right == null)
                root.right = newNode;
            else
                createBST(root.right, element);
        }else if(element < root.value){
            if(root.left == null)
                root.left = newNode;
            else
                createBST(root.left, element);
        }else{
            System.out.println("该节点" + element + "已存在");
            return;
        }
    }
    
    /*二叉树中查找元素*/
    public static void searchBST(BinaryTree root, int target, BinaryTree p){
        if(root == null){
            System.out.println("查找"+target+"失败");
        }else if(root.value == target){
            System.out.println("查找"+target+"成功");
        }else if(root.value >= target){
            searchBST(root.left, target, root);
        }else{ 
            searchBST(root.right, target, root);
        }
    }
    
    /*二叉树的中序遍历*/
    public static void midOrderPrint(BinaryTree rt){
        if(rt != null){
        	midOrderPrint(rt.left);
            System.out.print(rt.value + " ");
            midOrderPrint(rt.right);	
        }
    }
}

六、分块查找

public class BlockSearch {
	/*主表*/
    static int[] valueList = new int[]{
    	104, 101, 103, 105,102, 0, 0, 0, 0, 0,
        201, 202, 204, 203,0,   0, 0, 0, 0, 0,
        303, 301, 302,  0,   0,   0, 0, 0, 0, 0
    };

    /*索引表*/
    static Block[] indexList = new Block[]{
    	new Block(1, 0, 5),
    	new Block(2, 10, 4),
    	new Block(3, 20, 3)
    };
	
	public static void main(String[] args) {
		System.out.println("原始主表：");
		printElemts(valueList);
		
		/*分块查找*/
		int searchValue = 203;
		System.out.println("元素"+searchValue+"，在列表中的索引为："+blockSearch(searchValue)+"\n");
		
	    /*插入数据并查找*/
		int insertValue = 106;
		         
		/*插入成功，查找插入位置*/
	    if (insertBlock(insertValue)) {
		   System.out.println("插入元素"+insertValue+"后的主表：");
		   printElemts(valueList);
		   System.out.println("元素" + insertValue + "在列表中的索引为：" + blockSearch(insertValue));
	    }
	}
	
	public static void printElemts(int[] array) {
	    for(int i = 0; i < array.length; i++){
	        System.out.print(array[i]+" ");
	        if ((i+1)%10 == 0) {
	            System.out.println();
	        }
	    }
	}
	 
	 
	/*插入数据*/
	public static boolean insertBlock(int key) {
	    Block item = null;

	    /*确定插入到哪个块中，在该例子中，第一个block中放的是100-200之间的数，第二个block中放的是200-300之间的数，以此类推*/
	    int index = key/100;
	    int i = 0;
	    /*找到对应的block*/
	    for (i = 0; i < indexList.length; i++) {
	        if (indexList[i].index == index) {
	            item = indexList[i];
	            break;
	        }
	    }
	    /*如果数组中不存在对应的块，则不能插入该数据*/
	    if (item == null) {
	       return false;
	    }

	    /*将元素插入到每个块的最后*/
	    valueList[item.start + item.length] = key;
	    /*更新该块的长度*/
	    indexList[i].length++;
	    return true;
	} 
	 
	public static int blockSearch(int key) {
	    Block indexItem = null;

	    /*确定插入到哪个块中，在该例子中，第一个block中放的是100-200之间的数，第二个block中放的是200-300之间的数，以此类推*/
	    int index = key/100;
	    /*找到对应的block*/
	    for(int i = 0;i < indexList.length; i++) {
	       if(indexList[i].index == index) {
	           indexItem = indexList[i];
	           break;
	       }
	   }

	    /*如果数组中不存在对应的块，则返回-1，查找失败*/
	   if(indexItem == null)
	       return -1;

	   /*在对应的block中查找*/
	   for(int i = indexItem.start; i < indexItem.start + indexItem.length; i++) {
	       if(valueList[i] == key)
	           return i;
	    }
	   	return -1;
	}
}

七、哈希查找

public class HashSearch {

    /*待查找序列*/
    static int[] array = {13, 29, 27, 28, 26, 30, 38};
    /* 初始化哈希表长度，此处哈希表容量设置的和array长度一样。
     * 其实正常情况下，哈希表长度应该要长于array长度，因为使用
     * 开放地址法时，可能会多使用一些空位置
     */
    static int hashLength = 7;
    static int[] hashTable = new int[hashLength];

    public static void main(String[] args) {
        /*将元素插入到哈希表中*/
        for (int i = 0; i < array.length; i++) {
        	insertHashTable(hashTable, array[i]);
        }
        System.out.println("哈希表中的数据：");
        printHashTable(hashTable);
        
        int data = 28;
        System.out.println("\n要查找的数据"+data);
        int result = searchHashTable(hashTable, data);
        if (result == -1) {
            System.out.println("对不起，没有找到！");
        } else {
            System.out.println("在哈希表中的位置是：" + result);
        }
    }

    /*将元素插入到哈希表中*/
    public static void insertHashTable(int[] hashTable, int target) {
        int hashAddress = hash(hashTable, target);

        /*如果不为0，则说明发生冲突*/
        while (hashTable[hashAddress] != 0) {
            /*利用开放定址法解决冲突，即向后寻找新地址*/
            hashAddress = (++hashAddress) % hashTable.length;
        }

        /*将元素插入到哈希表中*/
        hashTable[hashAddress] = target;
    }

    public static int searchHashTable(int[] hashTable, int target) {
        int hashAddress = hash(hashTable, target);

        while (hashTable[hashAddress] != target) {
            /*寻找原始地址后面的位置*/
            hashAddress = (++hashAddress) % hashTable.length;
            /*查找到开放单元(未存放元素的位置)或 循环回到原点，表示查找失败*/
            if (hashTable[hashAddress] == 0 || hashAddress == hash(hashTable, target)) {
                return -1;
            }
        }
        return hashAddress;
    }

    /*用除留余数法计算要插入元素的地址*/
    public static int hash(int[] hashTable, int data) {
        return data % hashTable.length;
    }

    public static void printHashTable(int[] hashTable) {
    	for(int i=0;i<hashTable.length;i++)
    		System.out.print(hashTable[i]+" ");
    }
}