Algoritma Pemrograman 01 | Simple Search & Binary Search | Kuliah Online

Introduction

This tutorial provides a step-by-step guide to understanding and implementing Simple Search and Binary Search algorithms, as discussed in the lecture from Indonesia Belajar. These fundamental algorithms are essential in programming, especially when dealing with data search operations. By the end of this tutorial, you will have a clear understanding of both algorithms, their performance differences, and how to implement Binary Search in Python.

Step 1: Understanding Algorithms

• Definition: An algorithm is a step-by-step procedure or formula for solving a problem.
• Importance: Algorithms are crucial for data processing, enabling efficient problem-solving in programming.

Step 2: Introduction to Simple Search

• What is Simple Search: A straightforward method for finding a specific value within a list by checking each element one by one.
• How it works:
  1. Start at the beginning of the list.
  2. Compare the target value with each element.
  3. If a match is found, return the index; if not, continue until the end of the list.
• Complexity: The time complexity is O(n), meaning it can take longer as the list size increases.

Step 3: Introduction to Binary Search

• What is Binary Search: A more efficient algorithm that works on sorted lists by repeatedly dividing the search interval in half.
• How it works:
  1. Start with the entire list.
  2. Compare the target value to the middle element of the list.
  3. If the target matches the middle element, return the index.
  4. If the target is less than the middle element, repeat the search on the left half.
  5. If the target is greater, repeat on the right half.
• Complexity: The time complexity is O(log n), making it significantly faster for large datasets than Simple Search.

Step 4: Performance Comparison

• Simple Search vs. Binary Search:
  • Simple Search is intuitive but inefficient for large datasets.
  • Binary Search is more complex to implement but offers much better performance on sorted data.

Step 5: Understanding Logarithms

• Logarithm: A mathematical concept used to describe the time complexity of algorithms. In the context of Binary Search, it means the number of times you can divide the dataset until you reach a single element.

Step 6: Implementing Binary Search in Python

• Basic Implementation:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Target not found

• Explanation of Code:
  • The function takes a sorted list arr and a target value.
  • It initializes pointers for the left and right ends of the list.
  • It continues to narrow down the search until the target is found or the search space is empty.

Conclusion

In this tutorial, you learned the fundamentals of Simple Search and Binary Search algorithms, their implementations, and performance differences. Understanding these concepts is vital for efficient programming and data handling. Next steps could involve practicing these algorithms with varying datasets or exploring more complex algorithms to further enhance your programming skills.