Linear Search -Concept • Linear Search checks each element one by one • Works on unsorted or sorted data • Time Complexity: O(n)
3.
Linear Search -Python Code def linear_search(arr, x): for i in range(len(arr)): if arr[i] == x: return i return -1 # Example arr = [2, 4, 6, 8, 10] print(linear_search(arr, 8)) # Output: 3
4.
Binary Search -Concept • Binary Search repeatedly divides the array in half • Works only on sorted data • Time Complexity: O(log n)
5.
•Start with thefull array (low = 0, high = len(arr) - 1). •Find the middle element: mid = (low + high) // 2 •Compare arr[mid] with x: •If equal found at index mid. → •If arr[mid] < x search the → right half (low = mid + 1). •If arr[mid] > x search the → left half (high = mid - 1). •Repeat until low > high (which means element not found return - → 1).
6.
Binary Search -Python Code def binary_search(arr, x): """ Perform binary search on a sorted array. Parameters: arr (list): Sorted list of elements. x (any): Element to search for. Returns: int: Index of x in arr if found, otherwise -1. """ low = 0 high = len(arr) - 1
7.
while low <=high: mid = (low + high) // 2 # middle index if arr[mid] == x: # element found return mid elif arr[mid] < x: # search in right half low = mid + 1 else: # search in left half high = mid - 1 return -1 # not found # Example usage arr = [2, 4, 6, 8, 10] # must be sorted x = 8 result = binary_search(arr, x)
8.
Comparison: Linear vsBinary Search • • Linear Search: • - Simple, works on unsorted data • - O(n) time complexity • • Binary Search: • - Faster, works only on sorted data • - O(log n) time complexity • Use Linear Search for small/unsorted lists, • Binary Search for large/sorted lists.
![Linear Search - Python Code def linear_search(arr, x): for i in range(len(arr)): if arr[i] == x: return i return -1 # Example arr = [2, 4, 6, 8, 10] print(linear_search(arr, 8)) # Output: 3](https://image.slidesharecdn.com/linearvsbinarysearchpython-250911063835-1d52c044/75/Linear-search-Binary-search-complexity-analysis-3-2048.jpg)
![•Start with the full array (low = 0, high = len(arr) - 1). •Find the middle element: mid = (low + high) // 2 •Compare arr[mid] with x: •If equal found at index mid. → •If arr[mid] < x search the → right half (low = mid + 1). •If arr[mid] > x search the → left half (high = mid - 1). •Repeat until low > high (which means element not found return - → 1).](https://image.slidesharecdn.com/linearvsbinarysearchpython-250911063835-1d52c044/75/Linear-search-Binary-search-complexity-analysis-5-2048.jpg)
![while low <= high: mid = (low + high) // 2 # middle index if arr[mid] == x: # element found return mid elif arr[mid] < x: # search in right half low = mid + 1 else: # search in left half high = mid - 1 return -1 # not found # Example usage arr = [2, 4, 6, 8, 10] # must be sorted x = 8 result = binary_search(arr, x)](https://image.slidesharecdn.com/linearvsbinarysearchpython-250911063835-1d52c044/75/Linear-search-Binary-search-complexity-analysis-7-2048.jpg)
