Data Structures 17 - Sequential Search and Binary Search
Below, we provide a detailed introduction to sequential search and binary search in C, with particular attention to key-value pair scenarios. We will cover basic concepts, data structures, implementation methods, and code examples in a systematic manner.
I. Sequential Search
1. Concept
Sequential search is a simple search algorithm that starts from the first element of a dataset and checks each element one by one until the target element is found or the end of the dataset is reached. The time complexity of sequential search is (O(n)), where (n) is the size of the dataset.
2. Data Structure
We use an array to store key-value pairs. Key-value pairs can be represented using a struct.
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int key;
int value;
} KeyValuePair;
typedef struct {
KeyValuePair data[MAX_SIZE];
int size;
} SequentialTable;
3. Initializing the Sequential Table
When initializing the sequential table, we need to set the initial size to 0.
void initTable(SequentialTable *table) {
table->size = 0;
}
4. Adding Key-Value Pairs
Add key-value pairs to the sequential table.
bool addKeyValuePair(SequentialTable *table, int key, int value) {
if (table->size >= MAX_SIZE) {
return false; // Table is full
}
table->data[table->size].key = key;
table->data[table->size].value = value;
table->size++;
return true;
}
5. Sequential Search Function
Implement the sequential search function that returns the value corresponding to a given key.
int sequentialSearch(SequentialTable *table, int key) {
for (int i = 0; i < table->size; i++) {
if (table->data[i].key == key) {
return table->data[i].value;
}
}
return -1; // Not found
}
6. Complete Example Code
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int key;
int value;
} KeyValuePair;
typedef struct {
KeyValuePair data[MAX_SIZE];
int size;
} SequentialTable;
void initTable(SequentialTable *table) {
table->size = 0;
}
bool addKeyValuePair(SequentialTable *table, int key, int value) {
if (table->size >= MAX_SIZE) {
return false; // Table is full
}
table->data[table->size].key = key;
table->data[table->size].value = value;
table->size++;
return true;
}
int sequentialSearch(SequentialTable *table, int key) {
for (int i = 0; i < table->size; i++) {
if (table->data[i].key == key) {
return table->data[i].value;
}
}
return -1; // Not found
}
int main() {
SequentialTable table;
initTable(&table);
addKeyValuePair(&table, 1, 100);
addKeyValuePair(&table, 2, 200);
addKeyValuePair(&table, 3, 300);
int key = 2;
int value = sequentialSearch(&table, key);
if (value != -1) {
printf("Key %d found with value %d\n", key, value);
} else {
printf("Key %d not found\n", key);
}
return 0;
}
II. Binary Search
1. Concept
Binary search is an efficient search algorithm suitable for sorted arrays. It works by repeatedly halving the search range. The time complexity of binary search is (O(\log n)), where (n) is the size of the dataset.
2. Data Structure
Similar to sequential search, we use an array to store key-value pairs, ensuring that the array is sorted by key.
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int key;
int value;
} KeyValuePair;
typedef struct {
KeyValuePair data[MAX_SIZE];
int size;
} SortedTable;
3. Initializing the Sorted Table
When initializing the sorted table, we need to set the initial size to 0.
void initTable(SortedTable *table) {
table->size = 0;
}
4. Adding Key-Value Pairs
Add key-value pairs to the sorted table while maintaining the sorted order.
bool addKeyValuePair(SortedTable *table, int key, int value) {
if (table->size >= MAX_SIZE) {
return false; // Table is full
}
int i;
for (i = table->size - 1; (i >= 0 && table->data[i].key > key); i--) {
table->data[i + 1] = table->data[i];
}
table->data[i + 1].key = key;
table->data[i + 1].value = value;
table->size++;
return true;
}
5. Binary Search Function
Implement the binary search function that returns the value corresponding to a given key.
int binarySearch(SortedTable *table, int key) {
int left = 0;
int right = table->size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (table->data[mid].key == key) {
return table->data[mid].value;
} else if (table->data[mid].key < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Not found
}
6. Complete Example Code
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int key;
int value;
} KeyValuePair;
typedef struct {
KeyValuePair data[MAX_SIZE];
int size;
} SortedTable;
void initTable(SortedTable *table) {
table->size = 0;
}
bool addKeyValuePair(SortedTable *table, int key, int value) {
if (table->size >= MAX_SIZE) {
return false; // Table is full
}
int i;
for (i = table->size - 1; (i >= 0 && table->data[i].key > key); i--) {
table->data[i + 1] = table->data[i];
}
table->data[i + 1].key = key;
table->data[i + 1].value = value;
table->size++;
return true;
}
int binarySearch(SortedTable *table, int key) {
int left = 0;
int right = table->size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (table->data[mid].key == key) {
return table->data[mid].value;
} else if (table->data[mid].key < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Not found
}
int main() {
SortedTable table;
initTable(&table);
addKeyValuePair(&table, 1, 100);
addKeyValuePair(&table, 3, 300);
addKeyValuePair(&table, 2, 200);
int key = 2;
int value = binarySearch(&table, key);
if (value != -1) {
printf("Key %d found with value %d\n", key, value);
} else {
printf("Key %d not found\n", key);
}
return 0;
}
Summary
Sequential search and binary search are two common search algorithms, each with its own advantages and disadvantages. Sequential search is suitable for small or unordered datasets, while binary search is suitable for ordered datasets and performs better on large-scale datasets. The choice of search algorithm depends on the specific application scenario and data characteristics.
Written by Professor Min Fan
Code
/**
* Sequential search and binary search.
*
* @author Fan Min minfanphd@163.com.
*/
#include <stdio.h>
#include <malloc.h>
/**
* <key, value> pair.
*/
typedef struct Node{
int key;
char value;
}Node, *NodePtr;
/**
* The data structure of the sequential list.
*/
typedef struct SequentialList{
int length;
NodePtr elements;
}SequentialList, *ListPtr;
/**
* Initialize a data array.
*/
ListPtr initList(int* paraKeys, char* paraValues, int paraLength){
int i;
ListPtr resultPtr = (ListPtr)malloc(sizeof(struct SequentialList));
resultPtr->length = paraLength;
resultPtr->elements = (NodePtr)malloc((paraLength + 1) * sizeof(struct Node));
for (i = 0; i < paraLength; i ++){
//printf("setting key for index %d: %d and value: %c\r\n", i, paraKeys[i], paraValues[i]);
resultPtr->elements[i + 1].key = paraKeys[i];
resultPtr->elements[i + 1].value = paraValues[i];
}//Of for i
return resultPtr;
}//Of initList
/**
* Sequential search.
* @return The value.
*/
char sequentialSearch(ListPtr paraListPtr, int paraKey){
int i = paraListPtr->length;
paraListPtr->elements[0].key = paraKey;
paraListPtr->elements[0].value = 'x';
while(paraListPtr->elements[i].key != paraKey){
i--;
}//Of while
return paraListPtr->elements[i].value;
}//Of sequentialSearch
/**
* Test the sequential search function.
*/
void sequentialSearchTest() {
int tempUnsortedKeys[] = { 4, 5, 3, 6, 10, 7, 1, 9 };
char tempContents[] = { 'h', 'e', 'l', 'o', 'w', 'r', 'd', '!' };
ListPtr tempListPtr = initList(tempUnsortedKeys, tempContents, 8);
printf("Search result of 10 is: %c\r\n", sequentialSearch(tempListPtr, 10));
printf("Search result of 5 is: %c\r\n", sequentialSearch(tempListPtr, 5));
printf("Search result of 4 is: %c\r\n", sequentialSearch(tempListPtr, 4));
printf("Search result of 2 is: %c\r\n", sequentialSearch(tempListPtr, 2));
}// Of sequentialSearchTest
/**
* Binary search.
* @return The value.
*/
char binarySearch(ListPtr paraListPtr, int paraKey){
int tempLeft = 1;
int tempRight = paraListPtr->length;
int tempMiddle = (tempLeft + tempRight) / 2;
while (tempLeft <= tempRight) {
tempMiddle = (tempLeft + tempRight) / 2;
if (paraListPtr->elements[tempMiddle].key == paraKey) {
return paraListPtr->elements[tempMiddle].value;
} else if (paraListPtr->elements[tempMiddle].key <= paraKey) {
tempLeft = tempMiddle + 1;
} else {
tempRight = tempMiddle - 1;
}//Of if
} // Of while
// Not found.
return 'x';
}//Of binarySearch
/**
* Test the binary search function.
*/
void binarySearchTest() {
int tempUnsortedKeys[] = { 1, 3, 4, 5, 6, 7, 9, 10 };
char tempContents[] = { 'h', 'e', 'l', 'o', 'w', 'r', 'd', '!' };
ListPtr tempListPtr = initList(tempUnsortedKeys, tempContents, 8);
printf("Search result of 10 is: %c\r\n", binarySearch(tempListPtr, 10));
printf("Search result of 5 is: %c\r\n", binarySearch(tempListPtr, 5));
printf("Search result of 4 is: %c\r\n", binarySearch(tempListPtr, 4));
printf("Search result of 2 is: %c\r\n", binarySearch(tempListPtr, 2));
}// Of binarySearchTest
/**
* The entrance.
*/
int main(){
printf("\r\n-------sequentialSearchTest-------\r\n");
sequentialSearchTest();
printf("\r\n-------binarySearchTest-------\r\n");
binarySearchTest();
return 1;
}// Of main
Output
-------sequentialSearchTest-------
Search result of 10 is: w
Search result of 5 is: e
Search result of 4 is: h
Search result of 2 is: x
-------binarySearchTest-------
Search result of 10 is: !
Search result of 5 is: o
Search result of 4 is: l
Search result of 2 is: x
Press any key to continue