查找，也可称检索，是在大量的数据元素中找到某个特定的数据元素而进行的工作。查找是一种操作。

顺序查找

针对无序序列的一种最简单的查找方式。

时间复杂度为O(n)。

查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = (1+2+3+…+n)/n = (n+1)/2 ;

当查找不成功时，需要n+1次比较，时间复杂度为O(n);

优点： 
算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。 

缺点： 
查找效率低，因此，当n较大时不宜采用顺序查找。 

//顺序查找
int SequenceSearch(int a[], int value, int n)
{
    int i;
    for(i=0; i<n; i++)
        if(a[i]==value)
            return i;
    return -1;
}

//二分查找（折半查找），迭代版
int BinarySearch1(int a[], int value, int n)
{
  int low, high, mid;
  low = 0;
  high = n-1;
  while(low<=high)
  {
    mid = (low+high)/2;
    if(a[mid]==value)
      return mid;
    if(a[mid]>value)
      high = mid-1;
    if(a[mid]<value)
      low = mid+1;
  }
  return -1;
}
//二分查找，递归版本
int BinarySearch2(int a[], int value, int low, int high)
{
  int mid = low+(high-low)/2;
  if(a[mid]==value)
    return mid;
  if(a[mid]>value)
    return BinarySearch2(a, value, low, mid-1);
  if(a[mid]<value)
    return BinarySearch2(a, value, mid+1, high);
}

//插值查找
int InsertionSearch(int a[], int value, int low, int high)
{
  int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
  if(a[mid]==value)
    return mid;
  if(a[mid]>value)
    return InsertionSearch(a, value, low, mid-1);
  if(a[mid]<value)
    return InsertionSearch(a, value, mid+1, high);
}

     / * 分块查找 
     * 
     * @param index 索引表，其中放的是各块的最大值 
     * @param st 顺序表， 
     * @param key 要查找的值 
     * @param m 顺序表中各块的长度相等，为m 
     * @return 
     */ 
int BlockSearch(int[ ] index, int[ ] st, int key, int m)   //分块查找
    { 
          //  在序列st数组中，用分块查找方法查找关键字为key的记录 
         // 1.在index[ ] 中折半查找，确定要查找的key属于哪个块中  
          int i = BinarySearch(index, key);             
          if(i >= 0) 
          { 
              int j = i > 0 ? i * m : i; 
              int len = (i + 1) * m; 
              // 在确定的块中用顺序查找方法查找key 
              for(int k = j; k < len; k++)  
              { 
                  if(key == st[k]) 
                  { 
                      System.out.println("查询成功"); 
                      return k; 
                  } 
              } 
           } 
          System.out.println("查找失败"); 
          return -1; 
    } 
    
    int BinarySearchs(int[] data, int tmpData) 
    { 
        int mid; 
        int low = 0; 
        int high = data.length - 1; 
        while(low <= high) 
        { 
            mid = (low + high) / 2;     // 中间位置 
            if(tmpData =http://www.mamicode.com/= data[mid]) 
            { 
                return mid;             
            } 
            else if(tmpData < data[mid])     
            { 
                high = mid - 1; 
            } 
            else 
            { 
                low = mid + 1; 
                return low; 
            } 
        } 
        return -1;                // 没有查找到 
  }