This is the 7th day of my participation in the August More Text Challenge

The basic concept

  1. Lookup table: Consists of data elements (records) of the same type

  2. Static lookup tables: Only the lookup algorithm is required

  3. Dynamic lookup tables: In addition to lookup, data elements need to be added, deleted, or modified

  4. Keyword: A data item that uniquely identifies a data element

Common search algorithms

Binary search

concept

Split search, also known as binary search, only applies to the ordered list, can not use a linked list.

algorithm

Int search(seqlist L,Elemtype key) {int low,high= l.tablelen-1,mid; while(low<=high) { mid=(low<=high)/2; if(L.elem[mid]==key) return mid; else if(L.elem[mid]>key) high=mid-1; else low=mid-1; } return -1; }Copy the code

The construction of split – half search tree

  1. If there are an odd number of elements between LOW and HIGH, then the left and right parts have the same number of elements after MID is segmented

  2. If there is an even number of elements between the current LOW and HIGH, then the left part of the split MID has one less element than the right part

  3. If MID={(LOW=HIGH) /2} is rounded down, then there must be right subtree nodes – left subtree nodes =0 or 1 for any node

  4. A split – half search decision tree must be a balanced binary tree

  5. When the number of elements is N, the height of the tree h={log_2_ (n+1)} is rounded down

  6. Failed node: N +1 (equal to the number of empty chain domains of successful nodes)

Block to find

Block search, also known as index sequential search, algorithm process:

  1. Determine the block to which the record to look up belongs in the index table (either sequentially or in half)

  2. Look in the block

  3. If the index table does not contain the target keyword, the index table stops at LOW>HIGH and searches in the partition indicated by LOW (cause: The left side of LOW must be smaller than the target keyword, and the right side of HIGH must be larger than the target keyword). The index table of block storage stores the maximum key of each block.

  4. Set the average search length of index search and within block search to L1 and Ls respectively, then the average search length of block search is ASL=L1+Ls.

  5. L1= (1+2+… + block number)/block number = (block number +1) /2; Ls= (1+2+… Number of elements in each block)/ number of elements in each block =(Number of elements in each block +1)/2;