Searching Algorithms in Arrays

Introduction

• Discussed algorithms for searching elements in arrays
• Covered two main types: Linear Search and Binary Search

Linear Search

• Definition: Sequentially checks each element of the list until a match is found or the whole list has been searched.
• Steps:
  1. Compare each element with the key.
  2. If a match is found, return the index.
  3. If the element is not found, return -1.
• Implementation:
  • Get array size and elements from the user.
  • Get the key to search from the user.
  • Traverse the array and compare each element to the key.
  • Return the index if a match is found or -1 if not.
• Time Complexity: O(n)
  • In the worst case, the algorithm traverses the entire array.

Binary Search

• Definition: Searches a sorted array by repeatedly dividing the search interval in half.
• Steps:
  1. Check the middle element of the array.
  2. If it matches the key, return the index.
  3. If the key is smaller, repeat the search on the left half; otherwise, on the right half.
• Conditions: The array must be sorted.
• Example:
  • Given a sorted array and a key to find.
  • Compare key with the middle element.
  • Adjust search range based on comparison.
  • Repeat until the key is found or search range is exhausted.
• Implementation:
  • Initialize start and end pointers.
  • Loop until the start pointer is less than or equal to the end pointer.
  • Calculate the middle pointer.
  • Compare the middle element to the key.
  • Adjust start or end pointers based on comparison.
  • Return index if key is found or -1 if not.
• Time Complexity: O(log n)
  • The size of the search range is halved each iteration.

Time Complexity Analysis

• Explain why Binary Search is faster:
  • Array length reduces by half each iteration.
  • Complexity: O(log n) where n is the size of the array.
  • Fundamental comparison of logarithmic time vs linear time.

Conclusion

• Linear Search is simpler but less efficient: O(n)
• Binary Search is more efficient but requires sorted array: O(log n)
• Choosing the right algorithm depends on the array's properties and the scenario.

Thank you for your attention! See you in the next video.