Lookup (Searching) :

Is to determine a data element in a lookup table whose key is equal to the given value based on a given value

  • A Search Table is a collection of data elements (records) of the same type
  • A Key is the value of an item in a data element, also known as a Key, which can be used to represent a data element or to identify a data item (field) in a record. We call them keycodes
  • A Key is a Primary Key if it uniquely identifies a record
  • For keywords that identify multiple elements (records), we call them Secondary keys.

Static Search Table:

Lookup tables that do only lookup operations;

  1. Query whether a “specific” data element is in the lookup table;
  2. Retrieves a “specific” data element and various attributes;

Dynamic Search Table:

Insert non-existent data elements in the lookup table at the same time, or delete an existing data element from the lookup table; Obviously a dynamic lookup table operation is two actions

  1. Insert data elements when lookup;
  2. Delete data elements when lookup;

Sequential list lookup

In order to find

Sequential Search, also known as linear Search. It’s the most basic search technique. Its search process: start from the first (or the last) record in the table, one by one record keywords and the given value comparison;

  1. If the keyword of a record is equal to the specified value, the search succeeds and the searched record is found.
  2. If the comparison between the key and the given value is unequal until the last (or first) record, the table does not contain the record, and the search fails.

1.1 Ordinary Sequential Search

// a is the array,n is the number of arrays to be searched, and key is the keyword to be searched. int Sequential_Search(int *a,int n,int key){ for (int i = 1; i <= n ; i++) if (a[i] == key) return i; return 0; }Copy the code

1.2 Sentry sequence search

When we do a sequential lookup, we have to check whether we’re out of bounds, so we can use a sentinel, if the 0th bit of the array is empty, as the sentinel, and store it into the query. After the sentry is introduced, the value of the query must be found in the array. If it is found halfway through, the value is indeed present in the array. If it is found last, it is our sentry that is not in the array.

int SequentialSearch2(int *a, int n, int key) { int i = n; a[0] = key; while (a[i--] ! = key); return i; }Copy the code

Split search (binary search)

Keep narrowing the search by cutting it in half, save time.

int Binary_Search(int *a,int n,int key){ int low,high,mid; // define the lowest subscript as record first low = 1; // define the highest subscript as high = n; While (low <= high) {// mid = (low + high) /2; If (key < a[mid]) {// If (key < a[mid]) {// If (key < a[mid]) { high = mid-1; }else if(key > a[mid]){// if(key > a[mid]); low = mid+1; }else // mid = mid; return mid; } return 0; }Copy the code

The interpolation to find

The distribution of each data needs to be consistent. Query by calculating the offset of the query value in the whole range.

Int Interpolation_Search(int *a,int n,int key){int low,high,mid; low = 1; high = n; while (low<=high) { mid =low+(high-low)*(key-a[low])/(a[high]-a[low]); if (key < a[mid]) { high = mid-1; }else if(key > a[mid]){ low = mid+1; }else return mid; } return 0; }Copy the code

Fibonacci search

By using the property of increasing Fibonacci numbers, and in turn using the property of decreasing, to narrow the range.

Note that the part with insufficient quantity needs to be completed.

int F[100]; /* Fibonacci */ int Fibonacci_Search(int *a,int n,int key){int low,high,mid, I,k; // The lowest subscript is the first part of the record; low = 1; // The highest subscript is the last bit of the record; high = n; k = 0; //1. Calculate n as Fibonacci number position; while (n > F[k]-1) { k++; } //2. Insert into a; for(i = n; i < F[k]-1; i++) a[i] = a[n]; //3. While (low <= high) {// Calculate the current delimited subscript; mid = low+F[k-1]-1; If (key < a[mid]) {// If (key < a[mid]) { // Set the highest subscript to mid-1; high = mid-1; // Fibonacci subscript 1; k = k-1; }else if(key > a[mid]){// if(key > a[mid]); // Set low = mid+1; // Fibonacci subscript 2; k = k-2; }else{if (mid <= n) {// if (mid <= n); return mid; }else {// if mid>n, return n; return n; } } } return 0; }Copy the code