Searching and Sorting in Python
Subject: Data Structures and Algorithms · Language: Python · Level: beginner · 8 min read
Practice linear search, binary search, sort, sorted, searching/sorting logic, complexity, and Python DSA use cases.
Searching means finding whether a value, position, count, or condition exists in data. Sorting means arranging values in order. These two topics are connected because sorted data can often be processed more efficiently.
Linear search checks values one by one. It works on any list, whether sorted or unsorted. It is easy to understand, but for large input it can be slow because the worst case may require checking every element.
Binary search is faster, but it works correctly only on sorted data. It checks the middle value and removes half of the search space each time. This is why its time complexity is O(log n).
Sorting is useful when order helps solve the problem. Many two-pointer problems, duplicate problems, greedy problems, ranking problems, and interval problems become easier after sorting.
Students should remember that sorting changes the order of values. If the original index matters, store the original index before sorting or use a different approach. This is a common interview detail.
A strong problem-solving habit is to ask whether sorted order can simplify the logic. If yes, sorting may be a good first step. If no, searching or hashing may be better.
Searching and sorting are connected because sorted data can often be searched faster. For example, binary search works only when the data is sorted.
These two topics are important in DSA because many problems become easier after arranging data or quickly finding a required value.
What Is Searching?
Searching is the process of checking whether a value is present in a list, string, array-like structure, tree, graph, or other data structure.
For beginners, searching usually starts with lists. We check elements one by one or use a faster method if the list is sorted.
Linear Search
Linear search checks elements one by one from the beginning to the end.
It works on any list, whether the list is sorted or unsorted.
```python
index = -1
for i in range(len(arr)):
if arr[i] == target:
index = i
break
```
Here, `index` remains `-1` if the target is not found. If the target is found, we store its position and stop the loop using `break`.
Linear Search Example
Suppose the list is `[4, 1, 9, 2, 7]` and the target is `9`.
Linear search checks 4 first, then 1, then 9. When 9 is found, the search stops.
Linear Search Time Complexity
In the best case, the target is at the first position, so the time is O(1).
In the worst case, the target is at the last position or not present at all, so every element may be checked. The time complexity is O(n).
Linear search is simple and useful for small input or unsorted data.
What Is Sorting?
Sorting means arranging values in order. Most commonly, we sort numbers in increasing order or decreasing order.
For example, sorting `[4, 1, 9, 2, 7]` in increasing order gives `[1, 2, 4, 7, 9]`.
Sorting is useful because ordered data supports faster searching, two-pointer logic, duplicate handling, ranking, greedy choices, and interval problems.
Sorting in Python
Python provides two common ways to sort values: `sort()` and `sorted()`.
sort Method
The `sort()` method sorts the original list in place.
```python
arr = [4, 1, 9, 2, 7]
arr.sort()
```
After this, `arr` itself becomes `[1, 2, 4, 7, 9]`.
sorted Function
The `sorted()` function returns a new sorted list and does not change the original list.
```python
arr = [4, 1, 9, 2, 7]
sorted_arr = sorted(arr)
```
Use `sorted()` when you need to keep the original order safe.
Sorting in Decreasing Order
Use `reverse=True` to sort in decreasing order.
```python
arr.sort(reverse=True)
```
This is useful for ranking, selecting largest values, or greedy problems.
Binary Search
Binary search repeatedly checks the middle element and removes half of the search space.
Binary search is much faster than linear search for large sorted lists.
The most important rule is: binary search works correctly only when the data is sorted.
Binary Search Logic
Binary search keeps two boundaries: `left` and `right`.
```python
left = 0
right = len(arr) - 1
```
Then it calculates the middle index.
```python
mid = (left + right) // 2
```
If the middle value is the target, the search is complete. If the middle value is smaller than the target, search the right half. If it is larger, search the left half.
Binary Search Code
```python
left = 0
right = len(arr) - 1
index = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
index = mid
break
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
```
Here, `index` remains `-1` if the target is not found.
Binary Search Time Complexity
Binary search cuts the search space in half after every step. That is why its time complexity is O(log n).
For large input, O(log n) is much faster than O(n). This is why binary search is a very important DSA technique.
Common Sorting Algorithms
Even though Python provides built-in sorting, students should understand basic sorting algorithms.
Bubble sort repeatedly compares nearby elements and swaps them when they are in the wrong order. It is easy for beginners but slow for large input.
Selection sort repeatedly selects the smallest element from the unsorted part and places it at the correct position.
Insertion sort builds the sorted part one element at a time. It works well for small or nearly sorted data.
Merge sort divides the list into smaller parts, sorts them, and merges them back. Quick sort chooses a pivot and rearranges elements around it.
Beginners should first understand comparison and swapping using simple sorting. After that, divide-and-conquer sorting becomes easier.
When to Sort
Sort when order helps the problem. Common examples include binary search, two pointers, duplicate handling, ranking, interval merging, greedy problems, and finding closest pairs.
Sorting changes the order of the list if you use `sort()`. If the original order matters, use `sorted()` or make a copy first.
Searching in Python Using in
Python allows a quick membership check using `in`.
```python
if target in arr:
print("Found")
```
Sample Output when `target` exists in `arr`
```text
Found
```
This is simple, but it does not give the same learning value as writing search logic yourself. For DSA learning, understand linear search and binary search properly.
Example Program
```python
n = int(input("Enter size: "))
arr = list(map(int, input("Enter elements: " ).split()))
target = int(input("Enter target: "))
arr.sort()
left = 0
right = n - 1
index = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
index = mid
break
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
if index != -1:
print(f"Found at index {index} after sorting")
else:
print("Not found")
print("Sorted list:", *arr)
```
Sample Input
```text
5
4 1 9 2 7
9
```
Output
```text
Enter size: Enter elements: Enter target: Found at index 4 after sorting
Sorted list: 1 2 4 7 9
```
This program reads a list, sorts it, and then searches for the target using binary search. The printed index is the index after sorting, not necessarily the original index before sorting.
Searching and Sorting in DSA
Searching is used when we need to find a value, position, count, or condition. Sorting is used when order can simplify the problem.
Many DSA techniques depend on sorted data. Binary search, two pointers, greedy selection, and interval merging become easier after sorting.
A strong student should know when sorting is helpful and when it may destroy important original order.
Sorting is useful before two-pointer problems, duplicate handling, greedy selection, interval merging, ranking, and closest pair style problems. But sorting changes the original order, so be careful when original positions matter.
Practice Question
Take a list and a target value as input. First search the target using linear search. Then sort the list and use binary search to check whether the target exists.