Python : Linear search and Binary Search
Tags: algorithms, python, learning
Published: 2024-05-31 19:13:54

**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


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

### Calling function


```python
arr = [5,8,2,10,3,6]
key = 3
result = linear_search(key,arr)
```


```python
if result:
    print(f'Element {key} found at index {result}')
    
else:
    print("Element not found")
```

    Element 3 found at index 4
    

### 2nd calling


```python
key1 = 7
result1 = linear_search(key1,arr)
```


```python
if result1:
    print(f'Element {key1} found at index {result1}')
    
else:
    print("Element not found")
```

    Element not found
    

- 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


```python
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
```

### Calling Binary search


```python
arr = [2, 4, 6, 8, 10, 12, 14, 16]
key = 12
result = binary_search(key,arr)
```


```python
if result:
    print(f'Element {key} found at index {result}')
    
else:
    print("Element not found")
```

    Element 12 found at index 5
    

### 2nd Calling


```python
key = 1
result = binary_search(key,arr)
```


```python
if result:
    print(f'Element {key} found at index {result}')
    
else:
    print("Element not found")
```

    Element not found
    

- 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.