[Algorithms] Linear & Binary Search

Linear Search

• The time complexity for linear search is O(N), but its performance is dependent on its input:
  
  • Best Case: The algorithm requires only 1 comparison to find the target value in the first position of the list.
  • Worst Case: The algorithm requires only n comparison to find the target value in the last position of the list or does not exist in the list.
  • Average Case: The algorithm makes N/2 comparisons.

def linear_search(search_list, target_value):
  matches = []
  for idx in range(len(search_list)):
    if search_list[idx] == target_value:
      matches.append(idx)
  if matches is not None:
    return matches
  raise ValueError("{0} not in list".format(target_value))

def linear_search(search_list):
  maximum_score_index = None
  for idx in range(len(search_list)):
    if maximum_score_index is None or search_list[idx] > search_list[maximum_score_index]:
      maximum_score_index = idx
  return maximum_score_index​

• Linear search is a good choice for a search algorithm when:
  • You expect the target value to be positioned near the beginning of the list.
  • A search needs to be performed on an unsorted list because linear search traverses the entire list from beginning to end, regardless of its order.

---

Binary Search

• The time complexity is O(log N).
  • In each iteration, we are slicing the list in half.
  • ex) a sorted list of 64 elements will take at most log2(64) = 6 comparisons.

def binary_search(sorted_list, target):
  mid_idx = len(sorted_list)//2
  mid_val = sorted_list[mid_idx]

  if not sorted_list:
    return 'target not found'
  if mid_val == target:
    return mid_idx
  elif mid_val > target:
    left_half = sorted_list[:mid_idx]
    return binary_search(left_half, target)
  elif mid_val < target:
    # indices get shifted to the left by mid_idx
    right_half = sorted_list[mid_idx+1:]
    result = binary_search(right_half, target)
    if result == "target not found":
      return result
    else:
      return result + mid_idx + 1

• The solution above solves the problem of reducing the sorted input list by making a smaller copy of the list.
  • At each recursive call, we’re copying N/2 elements where N is the length of the sorted list.
  • We can do better by using pointers instead of copying the list.
  • Pointers are indices stored in a variable that mark the beginning and end of a list.
  • With pointers, we’ll track which sub-list we’re searching within the original input and there’s no need for copying.

 

Performing binary search iteratively:

def binary_search(sorted_list, target):
  left_pointer = 0
  right_pointer = len(sorted_list)
  
  while left_pointer < right_pointer:
    mid_idx = (left_pointer + right_pointer) // 2
    mid_val = sorted_list[mid_idx]
    if mid_val == target:
      return mid_idx
    if target < mid_val:
      right_pointer = mid_idx
    if target > mid_val:
      left_pointer = mid_idx + 1
  
  return "Value not in list"

 

Perfomring binary search recursively:

 

def binary_search(sorted_list, left_pointer, right_pointer, target):
  # this condition indicates we've reached an empty "sub-list"
  if left_pointer >= right_pointer:
    return "value not found"
	
  mid_idx = (left_pointer + right_pointer) // 2
  mid_val = sorted_list[mid_idx]

  if mid_val == target:
    return mid_idx
  if mid_val > target:
    # we reduce the sub-list by passing in a new right_pointer
    return binary_search(sorted_list, left_pointer, mid_idx, target)
  if mid_val < target:
    # we reduce the sub-list by passing in a new left_pointer
    return binary_search(sorted_list, mid_idx + 1, right_pointer, target)