Linear search is a simple search algorithm that sequentially checks each element in a list or array until the target element is found or the end of the list is reached. It starts from the beginning and compares each element with the target value until a match is found. If the target is found, it returns the index of the target element; otherwise, it returns -1 if the target is not present in the list. Linear search has a time complexity of O(n), where n is the number of elements in the list. It is suitable for small lists or unsorted data but becomes inefficient for large lists compared to other search algorithms like binary search.
//Linear Search
LinearSearch(list, target_element):
{
INITIALIZE index = 0
WHILE (index < number of items in the list)
{
IF (list[index] == target element)
{
RETURN index
}
INCREMENT index by 1
}
RETURN -1
}
Binary search is a method for finding a target value within a sorted array. It starts with defining pointers at the lowest and highest indices of the array. Then, it repeatedly halves the search interval by calculating the middle index. If the target is found at the middle index, the search terminates. Otherwise, it narrows the search range based on whether the target is greater or lesser than the element at the middle index. The process continues until the target is found or the search interval becomes empty. If the target is not found, -1 is returned.
//Binary Search
BinarySearch(array, target):
{
left = lowestBound(array)
right = highestBound(array)
WHILE (left <= right)
{
middle = (left + right) / 2
if(target = array[middle])
RETURN middle
else if(target < array[middle])
right = middle - 1
else
left = middle + 1
}
RETURN -1
}