Linear Searching
• Linear search, also known as a sequential search, is the simplest method for finding a
target element within a list or array.
• It works by sequentially checking each element from the beginning until a match is found
or the entire list has been traversed.
• This method is simple and works on unsorted data but becomes inefficient for very large
lists because it checks every item sequentially.
Linear Search Algorithm
1. Start from the first element (index 0) of the array.
2. Compare the current element with the target value you are searching for.
3. If they match, the element is found, and the search stops, often returning the index of the
element.
4. If they do not match, move to the next element in the array.
5. Repeat steps 2-4 until the target element is found or the end of the list is reached.
6. If the entire list is traversed without finding a match, the element is not present, and the
search typically returns a flag value like -1.
Example:
Consider the following array of numbers and a target value to search for:
Array: [10, 50, 30, 70, 80, 20, 90, 40]
Target value: 30
Step 1: Compare 30 with the first element, 10. They do not match.
Step 2: Compare 30 with the next element, 50. They do not match.
Step 3: Compare 30 with the next element, 30. They match! The search is successful,
and the index 2 is returned.
If, instead, you were searching for the value 60:
The algorithm would continue comparing until it reaches the end of the array at index 7
with 40.
Since no element matches 60, the search would conclude as unsuccessful and return -1.
Binary Searching
• Binary Search is an efficient algorithm for finding an item in a sorted list by repeatedly
dividing the search interval in half, a "divide and conquer" strategy that eliminates half
the data with each comparison, making it much faster than checking every item for large
datasets.
• It works by comparing the target value with the middle element; if they match, you're
done, but if not, you discard the half of the list where the target cannot be and repeat the
process on the remaining half.
Binary Search Algorithm
1. Start with a sorted array and define two pointers: low (first index) and high (last index).
2. Repeat the following steps as long as low is less than or equal to high:
i. Calculate the middle index: mid = low + (high - low) / 2.
ii. Compare the middle element (arr[mid]) with the target value:
o If they are equal, the element is found; return mid.
1
o If the target is greater than arr[mid], the target is in the right half.
Update low to mid + 1.
o If the target is smaller than arr[mid], the target is in the left half.
Update high to mid - 1.
3. If the loop finishes without finding the element (i.e., low becomes greater than high), the
target is not in the array; return -1.
Example:
Consider a sorted array: [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
Target value: 23 (search element)
Initial search space: Indices 0 to 9.
Step 1: Initial Setup and First Comparison
Initialize pointers:
low = 0 (index of the first element)
high = 9 (index of the last element)
Calculate the middle index:
mid = low + (high - low) / 2 = 0 + (9 - 0) / 2 = 4 (using integer division)
Compare the value at mid (16) with the target (23):
arr[4] is 16.
Since 16 < 23 (target is greater), the target must be in the right half of the array.
Adjust the search range:
Update low to mid + 1 (which is 5) to discard the left half.
New search space: Indices 5 to 9.
Step 2: Second Comparison
Calculate the new middle index:
mid = low + (high - low) / 2 = 5 + (9 - 5) / 2 = 5 + 4 / 2 = 7
Compare the value at mid (45) with the target (23):
arr[7] is 45.
Since 45 > 23 (target is smaller), the target must be in the left half of the current
search space.
Adjust the search range:
Update high to mid - 1 (which is 6) to discard the right half.
New search space: Indices 5 to 6.
Step 3: Third Comparison
Calculate the new middle index:
mid = low + (high - low) / 2 = 5 + (6 - 5) / 2 = 5 + 1 / 2 = 5
Compare the value at mid (23) with the target (23):
arr[5] is 23.
23 == 23. The target is found!
The algorithm returns the index 5, where the target value is located.