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

无序查找

最简单的无序查找为:

1
int sq_find(int arr[], int n, int key){
2
  
3
  for(int i = 0; i < n; i++){
4
    if(arr[i] == key)
5
       return i;
6
  }
7
  return -1;
8
}

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

1
int sq_find(int arr[], int n, int key){
2
3
  int i = n;
4
  arr[0] = key;
5
  while(arr[i] != key)
6
    i--;
7
  return i;
8
}

有序查找

二分查找

非递归实现

1
int BiSearch(int arr[], const int num, int begin, int end){
2
  
3
  int mid;
4
  if(begin > end){
5
    return -1;
6
  }
7
8
  while(begin <= end){
9
    mid = (begin+end) / 2;
10
    if(num[mid] == num){
11
      return mid;
12
    }else if(arr[mid] < num){
13
      begin = mid + 1;
14
    }else if(arr[mid] > num){
15
      end = mid - 1;
16
    }
17
  }
18
  return -1;
19
}

递归实现

1
int BiSearch(int arr[], const int num, int begin, int end){
2
  int mid = -1;
3
  mid = (begin + end) / 2;
4
  if(num == arr[mid]){
5
    return mid;
6
  }else if(num < arr[mid]){
7
    return BiSearch(arr, num, begin, mid-1);
8
  }else if(num > arr[mid]){
9
   return BiSearch(arr, num, mid+1, end);
10
  }
11
  return -1;
12
}

分块查找

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

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

1
struct indexBlock{
2
  int max;
3
  int start;
4
  int end;
5
}indexblock[4];
6
7
8
int blockSearch(int key, int a[]){
9
  int i = 0;
10
  int j;
11
12
  while(i<3 && key>indexblock[i].max)
13
    i++;
14
15
  if(i >= 3)
16
    return -1;
17
18
  j = indexblock[i].start;
19
20
  while(j<=indexblock[i].end && a[j] != key)
21
    j++;
22
23
  if(j > indexblock[i].end)
24
    j = -1;
25
26
  return j;
27
}