平均查找长度:
查找成功时的平均查找长度:
查找结构:
1 typedef int key_type; 2 typedef struct{ 3 key_type key; 4 info_type otherinfo; 5 }record_type; 6 typedef record_type elem_type; 7 typedef struct { 8 elem_type elem[MAXSIZE]; 9 int size; 10 }seq_list;
1 int seq_search(seq_list *r, key_type key) { 2 int i; 3 for(i = 0; i < r->size; i++) 4 if(r->elem[i].key == key) 5 return i; 6 return -1; 7 }
查找成功时的平均查找长度:(n+1)/2
查找不成功时的平均查找长度:n
折半查找要求元素先排序
1 int bin_search(seq_list *r, key_type key) { 2 int low = 0, high = r->size; 3 while(low < high) { 4 int mid = (low + high) / 2; 5 if(r->elem[mid].key == key) 6 return mid; 7 else if(r->elem[mid].key < key) 8 low = mid + 1; 9 else 10 high = mid; 11 } 12 return -1; 13 }
查找成功时的平均查找长度