Skip to content

Latest commit

 

History

History
82 lines (57 loc) · 4.05 KB

README.md

File metadata and controls

82 lines (57 loc) · 4.05 KB
Raw

made-with-Markdown GitHub last commit

Search Algorithms

Description • Resources • File Structure • Usage

Description

Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored. Based on the type of search operation, these algorithms are generally classified into two categories:

  • Sequential Search: In this, the list or array is traversed sequentially and every element is checked. For example: Linear Search.

  • Interval Search: These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half. For Example: Binary Search.

After this project I was able to explain these questions:

  • What is a search algorithm
  • What is a linear search
  • What is a binary search
  • What is the best search algorithm to use depending on your needs

Resources

Valuable resources to help you understand this project:

File structure

This table contains a brief description of the working files of the project, click on the names to get the source code.

All these files were compiled on Ubuntu 20.04 LTS using gcc.

Filename Description/Task 
0-linear.c
 Function that searches for a value in an array of integers using the Linear search algorithm 
1-binary.c
 Function that searches for a value in a sorted array of integers using the Binary search algorithm 
2-O
 What is the time complexity (worst case) of a linear search in an array of size n? 
3-O
 What is the space complexity (worst case) of an iterative linear search algorithm in an array of size n? 
4-O
 What is the time complexity (worst case) of a binary search in an array of size n? 
5-O
 What is the space complexity (worst case) of a binary search in an array of size n? 
6-O
 What is the space complexity of this function / algorithm? 
int **allocate_map(int n, int m)
{
  int **map;

  map = malloc(sizeof(int *) * n);
  for (size_t i = 0; i < n; i++)
  {
    map[i] = malloc(sizeof(int) * m);
  }
  return (map);
}
 
main_files
 Contain all the main file that will be used at compilation to test the functions above 
output_files
 Contain all the executable files generated after compilation

Usage

To try this project, first clone the repository to your machine :

$ git clone https://github.com/schambig/holbertonschool-low_level_programming.git

Then, go to the project directory:

$ cd search_algorithms

Finally, compile the source code you want:

$ gcc -Wall -Wextra -Werror -pedantic -std=gnu89 /PATH/main_files/[MAIN_FILE.c] [FILENAME.c] -o [EXECUTABLE_NAME]
Flag Description
-Wall Enable all the warnings in gcc
-Wextra Enable extra warnings that are not enabled by -Wall
-Werror Convert warnings into error
-pedantic Issue all warnings demanded by strict ISO C
-std=gnu89 Determine the language standard, in this case gnu89