# linear search and binary search in Python program

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:

1. Start from the first element of the array.
2. Compare the target value with the current element.
3. If it matches, return the index.
4. If not, move to the next element.
5. 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:

1. The array must be sorted before using binary search.
2. Start by setting two pointers, one at the start (left) and one at the end (right) of the array.
3. Find the middle element.
4. Compare the middle element with the target.
5. If it matches, return the index.
6. If the target is larger than the middle element, move the left pointer to the middle + 1.
7. If the target is smaller than the middle element, move the right pointer to the middle – 1.
8. 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
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:
``````

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

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

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:

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: