search algs

• Searching


  The process of finding a given value position in a list of values
• Searching Algorithms


  • Check for an element or retrieve an element from any data structure where it is stored
  • Generally classified into two categories: Sequential Search and Interval Search

  
• Sequential Search


  The list or array is traversed sequentially and every element is checked

  
• Sequential Search


  • Linear Search

  
• Interval Search


  • Specifically designed for searching in sorted data-structures
  • More efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half
• Interval Search


  • Binary Search
• Linear Search


  1. Traverse the array elements using a for loop

  2. Compare the search element with the current array element

  3. If the element matches, return the index

  4. If the element does not match, move to the next element

  5. If no match, return -1

  
• Linear search is widely used to search an element from the unordered list

  
• The worst-case time complexity of linear search is O(n)
• Linear Search


  • Best case: O(1)
  • Average case: O(n)
  • Worst case: O(n)
• The space complexity of linear search is O(1)
• Binary Search


  1. Divide the list into two halves

  2. Compare the search element with the middle element

  3. If match found, return the location

  4. If search element is smaller, search left half

  5. If search element is larger, search right half

  
• Binary search follows the divide and conquer approach
• Binary Search


  • Best case: O(1)
  • Average case: O(log n)
  • Worst case: O(log n)
• The space complexity of binary search is O(1)
• Jump Search


  Searches fewer number of elements compared to linear search by skipping some fixed number of array elements or jumping ahead by fixed number of steps in every iteration

  
• Interpolation Search


  • An improved variant of binary search that works on the probing position of the required value
  • Requires the data collection to be in sorted form and equally distributed

  
• Exponential Search


  • Also known as doubling or galloping search
  • Used to find the range where the search key may present
  • Then uses binary search to find the exact location

  
• Fibonacci Search


  A variant of binary search that uses the Fibonacci sequence or numbers to make a decision tree and search the key
• Sublist Search


  Used to detect the presence of one list in another list
• The sublist search algorithm compares the first element of the first list with the first element of the second list, and if they match, it checks the succeeding elements