查找是在一些(有序/无序)的数据元素中通过一定的方法找出与给定关键字相同的数据元素。

无序查找

最简单的无序查找为:

1
2
3
4
5
6
7
8

int sq_find(int arr[], int n, int key){
  
  for(int i = 0; i < n; i++){
    if(arr[i] == key)
       return i;
  }
  return -1;
}

对于这个for循环查找,一般的时间浪费在了i<n的边界检查上了,因此可以设置一个监视哨兵来优化无序查找:

1
2
3
4
5
6
7
8

int sq_find(int arr[], int n, int key){

  int i = n;
  arr[0] = key;
  while(arr[i] != key)
    i--;
  return i;
}

有序查找

二分查找

非递归实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int BiSearch(int arr[], const int num, int begin, int end){
  
  int mid;
  if(begin > end){
    return -1;
  }

  while(begin <= end){
    mid = (begin+end) / 2;
    if(num[mid] == num){
      return mid;
    }else if(arr[mid] < num){
      begin = mid + 1;
    }else if(arr[mid] > num){
      end = mid - 1;
    }
  }
  return -1;
}

递归实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int BiSearch(int arr[], const int num, int begin, int end){
  int mid = -1;
  mid = (begin + end) / 2;
  if(num == arr[mid]){
    return mid;
  }else if(num < arr[mid]){
    return BiSearch(arr, num, begin, mid-1);
  }else if(num > arr[mid]){
   return BiSearch(arr, num, mid+1, end);
  }
  return -1;
}

分块查找

分块查找又叫索引顺序查找,是介于顺序查找与二分查找之间的一种查找方法。在二分查找中要求数据按关键字排序且有序,这一条件下在数目很大且动态变化的情况下很难满足,而分块查找优化了这种条件下的查找。

分块查找需要建立索引表,索引表是分段有序的,而数据集合可以使无序的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

struct indexBlock{
  int max;
  int start;
  int end;
}indexblock[4];


int blockSearch(int key, int a[]){
  int i = 0;
  int j;

  while(i<3 && key>indexblock[i].max)
    i++;

  if(i >= 3)
    return -1;

  j = indexblock[i].start;

  while(j<=indexblock[i].end && a[j] != key)
    j++;

  if(j > indexblock[i].end)
    j = -1;

  return j;
}