DEV Community

Nitin Kendre
Nitin Kendre

Posted on

Python : Linear search and Binary Search

#algorithms #python #learning

Practicing Python From Basics

Linear Search:

  • Linear search, also known as sequential search, checks each element in a collection one by one until the target element is found or the end of the collection is reached.
  • It's a simple but inefficient algorithm, especially for large datasets, as it has a time complexity of O(n) in the worst case.
  • Linear search is applicable to both sorted and unsorted collections.

Implementation 

def linear_search(key,arr):
    for index in range(len(arr)):
        if arr[index] == key:
            return index

    return 0
Enter fullscreen mode Exit fullscreen mode

Calling function 

arr = [5,8,2,10,3,6]
key = 3
result = linear_search(key,arr)
Enter fullscreen mode Exit fullscreen mode 
if result:
    print(f'Element {key} found at index {result}')

else:
    print("Element not found")
Enter fullscreen mode Exit fullscreen mode 
Element 3 found at index 4
Enter fullscreen mode Exit fullscreen mode

2nd calling 

key1 = 7
result1 = linear_search(key1,arr)
Enter fullscreen mode Exit fullscreen mode 
if result1:
    print(f'Element {key1} found at index {result1}')

else:
    print("Element not found")
Enter fullscreen mode Exit fullscreen mode 
Element not found
Enter fullscreen mode Exit fullscreen mode
  • The linear_search function takes a list arr and a target value key.
  • It iterates through each element of the list using a for loop.
  • For each element, it checks if it matches the target value.
  • If a match is found, it returns the index of the element. If not found, it returns 0.

Binary Search

  • Binary search is a more efficient algorithm for finding a target value within a sorted array.
  • It repeatedly divides the search interval in half until the target is found or the interval is empty.
  • Binary search has a time complexity of O(log n), making it significantly faster than linear search for large datasets.
  • It requires the array to be sorted beforehand.

Implementation 

def binary_search(key,arr):
    start, end = 0, len(arr)-1

    while start<=end:
        mid = (start+end)//2

        if arr[mid] == key:
            return mid

        elif arr[mid]<key:
            start = mid+1

        else:
            end = mid-1

    return 0
Enter fullscreen mode Exit fullscreen mode

Calling Binary search 

arr = [2, 4, 6, 8, 10, 12, 14, 16]
key = 12
result = binary_search(key,arr)
Enter fullscreen mode Exit fullscreen mode 
if result:
    print(f'Element {key} found at index {result}')

else:
    print("Element not found")
Enter fullscreen mode Exit fullscreen mode 
Element 12 found at index 5
Enter fullscreen mode Exit fullscreen mode

2nd Calling 

key = 1
result = binary_search(key,arr)
Enter fullscreen mode Exit fullscreen mode 
if result:
    print(f'Element {key} found at index {result}')

else:
    print("Element not found")
Enter fullscreen mode Exit fullscreen mode 
Element not found
Enter fullscreen mode Exit fullscreen mode
  • The binary_search function takes a sorted array arr and a target value key.
  • It initializes start and end pointers to the start and end of the array, respectively.
  • It repeatedly calculates the mid index and compares the element at mid with the key.
  • Based on the comparison, it updates start or end pointers to narrow down the search interval.
  • It continues until the target is found or the search interval is empty, returning the index of the target or 0 if not found.

Top comments (0)