Searching Algortihms

• Searching

  Determining whether a value (search key) is present in the data and, if so, finding the value's location
• Comparison-based search algorithms

  • Sequential search
  • Binary search

  
• Sequential search

  • Works the same for both array-based and linked lists
  • Compares the key element sequentially with each element in the array
  • Continues until the key matches an element or the array is exhausted
  • Returns the index of the matching element or -1 if no match is found

  
• Sequential search algorithm for array-based lists

  1. Compare the key element sequentially with each element in the array

  2. Continue until the key matches an element or the array is exhausted

  3. If a match is found, return the index of the matching element

  4. If no match is found, return -1

  
• Sequential search is also called linear search
• When analysing search algorithms

  We count the number of comparisons

  
• Unsuccessful sequential search

  • Requires the examination of every item in the list
  • Makes n comparisons
  • Time is O(n)

  
• Successful sequential search

  • Number of key comparisons depends on where in the list the search item is located
  • Best case: search item is the first element, makes 1 comparison, O(1)
  • Worst case: search item is the last element, makes n comparisons, O(n)

  
• Sequential search works well for small arrays or unsorted arrays
• Sequential search is inefficient for large arrays
• Binary search


  Requires ordered lists<|>Uses the divide-and-conquer technique to search the list

  
• Binary search algorithm

  1. First compares the key with the element in the middle of the array

  2. If the key is less than the middle element, continue searching the first half

  3. If the key is equal to the middle element, the search ends with a match

  4. If the key is greater than the middle element, continue searching the second half

  
• Binary search is performed only on ordered lists

  
• Ordered lists

  • Elements are ordered according to some criteria, usually ascending order
  • Operations are the same as unordered lists, plus insertion in order
• Insertion in an ordered list


  After insertion, the resulting list must be ordered

  
• Sequential search is O(n) and binary search is O(log2n)

  
• There is a lower bound on comparison-based search algorithms
• Comparison-based search algorithms cannot be made faster than O(log2n)