常见查询算法

====================
顺序查找算法
====================
1. 算法描述
顺序逐一比较即可。

2. 平均查找长度
(n+1)/2, 其中n为表长。

3. 算法实现


4. 优化思想
根据经验，目前被查到越多的元素，将来可能被查到的可能性也越大。所以可以考虑，每次查找到一个元素后，将它和直接前驱交换位置。
如果上述的经验从概率上来讲是成立的，则可以加快顺序查找的速度。


====================
二分查找算法
====================
1. 算法描述
限制：待查表必须是有序的向量(在内存中连续存储)
首先和数组中点比较，如果等于则返回，如果小于中点则在左边区间查找，如果大于中点则在右边区间查找。

2. 平均查找长度
lg(n+1)

3. 算法实现
(1) 非递归方式

(2) 递归方式

/**
* 功能：二分查找
*/
public class DemoFind{

public static void main(String[] arg){
int arr[]={2,4,5,7,8,97};
BinaryFind bf=new BinaryFind();
bf.find(0,arr.length-1,8,arr);
}
}

class BinaryFind
{
public void find(int leftIndex,int rightIndex,int val,int arr[]){

int midIndex=(rightIndex+leftIndex)/2;
int midVal=arr[midIndex];

if(leftIndex<=rightIndex){
if(midVal>val){
//在arr左边数中找
find(leftIndex,midIndex-1,val,arr);   //简单递归
}
else if(midVal<val){
//在arr右边数中找
find(midIndex+1,rightIndex,val,arr);
}
else if(midVal==val){
System.out.println("找到下标"+midIndex);
}
}
}
}

BinaryFind

====================
分块查找算法
====================
1. 基本思想
以增加空间复杂度为代价(存储每块中的最大值已经最大值的位置)，为原数组做一个索引(索引本身是递增有序的)，这样先查索引，再查块内位置。如果索引的选择科学有效，则可以获得比顺序查找快的速度。

2. 算法描述
抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即: ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。
先用二分法查到元素可能所在的块起始位置，而后在块内进行顺序查找。
（将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。）

3. 平均查找长度
平均查找长度在顺序查找和二分查找之间，并且当结点数为元素数量的平方根时，查找长度最小。

=======================
二叉排序树上的查找
=======================
1. 基本思想
由如何改进二分查找的缺陷(插入和删除操作需要移动大量的数据)而得出的一种算法，用二叉排序树存储数据，由于二叉树的插入和删除操作的时间复杂度相对低，而且也支持二分查找，所以在动态数据查找方面优于二分查找。

2. 算法描述
二叉树的特点是中序遍历可以得到递增的序列。很容易可以得出在二叉排序树上进行二分排序的递归代码。

3. 平均查找长度
和二叉排序树的形态有关。在极端情况下，二叉树只有单一的左或右分支，则查找长度为(n+1)/2；如果是平衡二叉树，则查找长度为lgn(树的层次)。

=======================
散列技术下的查找
=======================
1. 基本思想
将元素的值和其位置直接对应，对应的方法就是散列函数(如平方取中，除余法等等)；然而再好的散列函数也会引起冲突，则解决冲突的方法是如拉链法，线性探测法，二次探测法等等。

//查出最大值和最小值

package com.think;

import java.util.Scanner;


public class ArrayTest {

    public static void main(String[] args) {
    //    int[] nums = { 2, 1, 4, 100, 88, 66, 123, 5, 74, 69 };
        
        //从控制台输入
        Scanner sin=new Scanner(System.in);
        int []numbers =new int[10];
        //接受的数据放到数组中
        for(int t=0;t<numbers.length;t++){
            numbers[t]=sin.nextInt();
        }
        for(int num:numbers){
            System.out.print(num+",");
        }
        
        //顺序排序
        /*for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]>nums[j]){
                int temp=nums[i];
                nums[i]=nums[j];
                nums[j]=temp;
            }
            }
        }
        
          System.out.println("最小值为:" + nums[0] + " , 最大值为:"
            + nums[nums.length - 1]);
          
         System.out.println("排序后的数组为：");
          for(int i :nums){
              System.out.print(i+",");
          }
*/
    }

}