In this Python tutorial, we will discuss, **linear search and binary search in Python program**. This tutorial will walk you through implementing two of the most fundamental search algorithms: linear search and binary search in Python. You will also learn to **implement binary search without using functions**.

## linear search and binary search in Python

Searching is a common operation in computer science, where you need to find a particular value from a collection of values. Two common algorithms for this operation are linear search and binary search.

### Linear Search:

- In linear search, you start from the first element and compare each element with the target value until you find a match.
- Time Complexity: O(n)

**How it works:**

- Start from the first element of the array.
- Compare the target value with the current element.
- If it matches, return the index.
- If not, move to the next element.
- Repeat steps 2-4 until you find the target or reach the end of the array.

**Performance:**

- Time complexity is O(n) because, in the worst-case scenario, it checks each element in the array.
- No requirement for the array to be sorted.

### Binary Search:

- In binary search, the array must be sorted. You repeatedly divide the array into halves until the value is found.
- Time Complexity: O(log n)

**How it works:**

- The array must be sorted before using binary search.
- Start by setting two pointers, one at the start (left) and one at the end (right) of the array.
- Find the middle element.
- Compare the middle element with the target.
- If it matches, return the index.
- If the target is larger than the middle element, move the left pointer to the middle + 1.
- If the target is smaller than the middle element, move the right pointer to the middle – 1.
- Repeat steps 3-7 until you find the target or the pointers cross (left > right).

**Performance:**

- Time complexity is O(log n) because it effectively halves the search space with each iteration.
- Requires the array to be sorted.

## Linear Search in Python

### Implementing Linear Search

Here’s a step-by-step guide to implementing a linear search algorithm in Python:

```
def linear_search(arr, target):
# Loop through each element in the array
for index, element in enumerate(arr):
# If the element matches the target, return the index
if element == target:
return index
# If the loop finishes, the target was not found
return -1
```

### Example: Linear Search Program in Python

Let’s write a Python program for linear search to find the index of a target value in an array.

```
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
# Example array and target value
arr = [4, 2, 7, 1, 9, 3]
target = 7
# Call the linear_search function
index = linear_search(arr, target)
# Output the result
if index != -1:
print(f"Element {target} found at index {index}")
else:
print(f"Element {target} not found in the array")
```

You can see the output:

## Binary Search in Python

### Implementing Binary Search with a Function

Here’s a step-by-step guide to **implementing binary search using a function**:

```
def binary_search(arr, target):
left, right = 0, len(arr) - 1
# Continue the search while the left index is less than or equal to the right index
while left <= right:
mid = (left + right) // 2
# Check if the target is present at mid
if arr[mid] == target:
return mid
# If target is greater, ignore the left half
elif arr[mid] < target:
left = mid + 1
# If target is smaller, ignore the right half
else:
right = mid - 1
# If we reach here, the element was not present
return -1
```

### Example: Binary Search Program in Python

Let’s see a Python program to implement binary search using the above function.

```
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Example sorted array and target value
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
# Call the binary_search function
index = binary_search(arr, target)
# Output the result
if index != -1:
print(f"Element {target} found at index {index}")
else:
print(f"Element {target} not found in the array")
```

You can see the output like below:

## Implement Binary Search Without a Function

Here’s how you can **write a Python program to implement binary search without using a function**.

### Example: Binary Search in Python Without a Function

```
# Example sorted array and target value
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
# Set initial left and right indices
left, right = 0, len(arr) - 1
# Binary search without function
while left <= right:
mid = (left + right) // 2
# Check if target is present at mid
if arr[mid] == target:
print(f"Element {target} found at index {mid}")
break
# If target is greater, ignore the left half
elif arr[mid] < target:
left = mid + 1
# If target is smaller, ignore the right half
else:
right = mid - 1
else:
print(f"Element {target} not found in the array")
```

You can see the output below in the screenshot.

## Linear Search and Binary Search in Python

Here is a comparison of Linear Search and Binary Search in Python in a tabular format:

Aspect | Linear Search | Binary Search |
---|---|---|

Algorithm Type | Sequential Search | Interval Search |

How it works | Sequentially checks each element for a match | Repeatedly divides the search interval in half |

Sorted Data Required | No, works on both sorted and unsorted arrays | Yes, only works on sorted arrays |

Time Complexity | O(n) | O(log n) |

Space Complexity | O(1) | O(1) |

Implementation | Easier | Slightly more complex |

Performance | Slower for large datasets | Faster for large datasets |

Best-case Scenario | O(1), when the element is at the first position | O(1), when the element is at the middle position |

Worst-case Scenario | O(n), when the element is at the last position or not present | O(log n) |

Use Cases | Small datasets, unsorted data | Large datasets, sorted data |

This table summarizes the key differences between **linear search and binary search algorithms in Python**.

## Conclusion

This tutorial has covered how to implement **linear search and binary search in Python**, including examples with and without using functions. Whether you’re looking to write a python program to implement linear search and binary search, or specifically focusing on binary search in Python without using a function, this tutorial has you covered.

You may also like:

- Fastest sorting algorithm in Python
- raw input function in Python
- get values from json array in Python
- Add two binary numbers in Python

I am Bijay Kumar, a Microsoft MVP in SharePoint. Apart from SharePoint, I started working on Python, Machine learning, and artificial intelligence for the last 5 years. During this time I got expertise in various Python libraries also like Tkinter, Pandas, NumPy, Turtle, Django, Matplotlib, Tensorflow, Scipy, Scikit-Learn, etc… for various clients in the United States, Canada, the United Kingdom, Australia, New Zealand, etc. Check out my profile.