In the context of data structures, searching refers to the process of finding a specific value or item in a data structure such as a list, array, or dictionary using Python. The most commonly used searching algorithms are linear search and binary search.
Linear search is a simple algorithm that involves iterating through each element in a list or array until the desired value is found. Here's an example of how to implement a linear search algorithm in Python:
```python
def linear_search(array, target):
for i in range(len(array)):
if array[i] == target:
return i
return -1
```
Binary search is a more efficient algorithm that is used to search sorted lists or arrays. It works by repeatedly dividing the search interval in half until the target value is found. Here's an example of how to implement a binary search algorithm in Python:
```python
def binary_search(array, target):
low = 0
high = len(array) - 1
while low <= high:
mid = (low + high) // 2
if array[mid] == target:
return mid
elif array[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
```
Both linear search and binary search have their own advantages and disadvantages, and the choice of algorithm depends on the specific use case and the size of the data being searched.
Sure, here's an example of how to implement linear search in Python:
```python
def linear_search(array, target):
for i in range(len(array)):
if array[i] == target:
return i
return -1
```
In this example, the `linear_search` function takes an array and a target value as inputs. The function then iterates through each element of the array using a `for` loop and checks if the current element matches the target value. If a match is found, the function returns the index of the matching element. If no match is found after iterating through the entire array, the function returns -1 to indicate that the target value was not found.
Here's an example usage of the `linear_search` function:
```python
array = [5, 10, 15, 20, 25, 30]
target = 20
result = linear_search(array, target)
print(result) # Output: 3
```
In this example, we define an array `[5, 10, 15, 20, 25, 30]` and a target value `20`. We then call the `linear_search` function with these inputs and store the result in the `result` variable. The function returns the index `3` because the value `20` is located at index `3` in the array. We then print the result to the console.
Certainly, here's an example of how to implement binary search in Python:
```python
def binary_search(array, target):
low = 0
high = len(array) - 1
while low <= high:
mid = (low + high) // 2
if array[mid] == target:
return mid
elif array[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
```
In this example, the `binary_search` function takes a sorted array and a target value as inputs. The function first sets `low` and `high` variables to the first and last indices of the array, respectively. The function then enters a loop that continues as long as `low` is less than or equal to `high`.
Within the loop, the function calculates the `mid` index as the floor division of the sum of `low` and `high` by `2`. It then checks if the value at the `mid` index matches the target value. If it does, the function returns the `mid` index. If the value at the `mid` index is less than the target value, the function updates the `low` index to `mid + 1`. If the value at the `mid` index is greater than the target value, the function updates the `high` index to `mid -1`.
If the target value is not found after the loop has completed, the function returns -1 to indicate that the target value was not found in the array.
Here's an example usage of the `binary_search` function:
```python
array = [5, 10, 15, 20, 25, 30]
target = 20
result = binary_search(array, target)
print(result) # Output: 3
```
In this example, we define a sorted array `[5, 10, 15, 20, 25, 30]` and a target value `20`. We then call the `binary_search` function with these inputs and store the result in the `result` variable. The function returns the index `3` because the value `20` is located at index `3` in the array. We then print the result to the console.
Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.
We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc