Search Algorithms (Linear, Binary)

algorithmic thinking is to clearly define what the problem set is interviewers don't care that you are able to write a specific algorithm in code but more about the fact that you can break a seemingly insurmountable problem into distinct components and identify the right tools to solve each distinct component.

 

Algorithm follows a certain set of guidelines and use the same steps to solve the problem each time we face it

Algorithms must first have a clear problem statement, having on idea what you are trying to solve

Linear / Sequential Search

Defining a problem, need to specify how the input is defined and what the output looks like when the algorithm has done it's job.

Linear search algorithm is a simple search algorithm used to find the location of a  target value within a list or array of elements. The algorithm works by sequentially checking each element of the list, starting from the first element, until the target value is found or until the end of the list is reached.

 

Algorithm definition must have a specific set of instructions in a particular order

 

1. start at beginning
2. compare current value to target
3. move sequentially
4. reach end of the list
   

Each step must be a distinct one which means it cannot add extra subtasks.

The input must be series of values!

Algorithms should provide a result and should actually complete, not take an infinite amount of time

def linear_search(list, target):
    """Returns the index position of the target if found, else returns None"""
    
    # from 0 to length of list, if list is in the target, return the target index number
    # think of linear cost, the len(list) is a constant time operation, keeping track of the length
    for i in range(0, len(list)):
        # subscript notation 
        if list[i] == target:
            return i 
    return None

# function accepting an index value, prints out whether target was found or not 
def verify(index):
    if index is not None: 
        print(f"Number {index + 1}: Target found at index: ", index)
    else:
        print("Target not found in list")

numbers = [x for x in range(1,11)]

result = linear_search(numbers, 12)
verify(result)

result = linear_search(numbers, 6)
verify(result)

WORK THROUGH THE GUIDELINE

Break down the problems into any possible number of smaller problems where each problem can be clearly defined in terms of input and an output

 

---

Binary Search

Binary search is a search algorithm used to find the position of a target value within a sorted array of elements. The algorithm works by repeatedly dividing the search interval in half until the target value is found or determined to be not present in the array.

 

In these algorithms, the values needs to be sorted first. It is a search algorithm , so we are providing something to search for and instead it returns the position in the list that the target occupies

Without the list being sorted, a binary search algorithm would discard all the values to the left or right.

 

First the input, a sorted list of values, the output = position in the list of the target value we're searching for or some sort of values indicate that the target does not exist in the list

---

Steps of Binary Search :

 

1. start from the middle of the list
2. compare the element in the middle position to the target element
3. if the elements match, we return the middle position and end
4. if don't match, check whether the element in the middle position is smaller than the target element
   1. then go back to step 2 with a new list that goes from the middle position of the current list to the end of the current list
5. if the element in the middle position is greater than the target element, then go back to step 2 with a new list that goes from the start to the middle of the current list
6. repeat until the target element is found, or until the sub list contains only one element
   1. if doesn't reach the target even when there's only one element, then it DOES NOT EXIST (DNE)
      

def binary_search(list, target):
    # keep track of the list we're working with 
    first = 0
    last = len(list) - 1
    
    """
    keep executing the loop until the value of first is less than or equal to last 
    inside while loop, calculate the midpoint of the list (first step)
    the while loop causes the run time to grow 
    """ 
    while first <= last:
        # use floor division operator, rounding down to nearest whole number  
        midpoint = (first + last)//2
        #compare the midpoint to the target 
        if list[midpoint] == target:
            return midpoint        
        elif list[midpoint] < target:
            first = midpoint + 1
        else:
            last = midpoint - 1
    # if it wasn't in the list 
    return None

def verify(index):
    if index is not None: 
        print(f"Number {index + 1}: Target found at index:", index)
    else:
        print(f"Number {index}: Target not found in list")
        
numbers = [x for x in range(1,11)]
print(numbers)

result = binary_search(numbers, 12)
verify(result)

# if looking for 6 with binary search, the `first = midpoint + 1` will activate, making first 5, + last (9-1) = 8 in this case 
result = binary_search(numbers, 6)
verify(result)
# if the values are unsorted, binary serach might return none even if the value exists in the list

 

These two are the very basic search algorithms that we will always run into in the future.