Linear Search and Binary Search

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

Searching algorithms

Searching is an essential operation
- Several ways
Algorithms that search for an element within a collection:
- Linear search
- Binary search

Linear search

Looping through each element

A schematic representation of a list of unordered numbers.

Element found
- algorithm stops
- returns the result
Element not found
- algorithm continues

Linear search

def linear_search(unordered_list, search_value):

  for index in range(len(unordered_list)):

    if unordered_list[index] == search_value:

      return True

  return False

print(linear_search([15,2,21,3,12,7,8], 8))

True

print(linear_search([15,2,21,3,12,7,8], 800))

False

Linear search - complexity

Complexity: $O(n)$

Binary search

Only applies to ordered lists

Schematic representation of a list containing ordered numbers.

15 ???

Binary search

Only applies to ordered lists

Schematic representation of a list containing ordered numbers. There is a variable called first that points to the first position of the list.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Binary search

Only applies to ordered lists

Schematic representation of a list containing ordered numbers. There is a variable called first that points to the first position of the list and another variable called last that points to the last position.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1


  while first <= last:

Binary search

Only applies to ordered lists

Schematic representation of a list containing ordered numbers. There is a variable called first that points to the first position of the list, another variable called last that points to the last position, and another variable called middle that points to the middle position.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

Binary search

Only applies to ordered lists

15 ???
Compare search_value with the item in the middle of the list

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

    if search_value == ordered_list[middle]:

      return True

    elif search_value < ordered_list[middle]:

Binary search

Only applies to ordered lists

Schematic representation of a list containing ordered numbers. There is a variable called first that points to the first position of the list, another variable called last that points to the middle position minus one, and another variable called middle that points to the middle position. The elements that are between the first and middle positions are colored in green.

15 ???
Compare search_value with the item in the middle of the list

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1

Binary search

Only applies to ordered lists

15 ???
Compare search_value with the item in the middle of the list

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:

Binary search

Only applies to ordered lists

Schematic representation of a list containing ordered numbers. There is a variable called first that points to the middle position plus one, another variable called last that points to the last position, and another variable called middle that points to the middle position. The elements that are between the first and middle positions are colored in green.

15 ???
Compare search_value with the item in the middle of the list

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binary search

Only applies to ordered lists

Schematic representation of a list containing ordered numbers. The middle pointer has moved and points at the element located between first and the last. The elements that are between the first and middle positions are colored in green.

15 ???
Compare search_value with the item in the middle of the list

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binary search

Only applies to ordered lists

15 ???
Compare search_value with the item in the middle of the list

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binary search

Only applies to ordered lists

Schematic representation of a list containing ordered numbers. The last pointer has been moved and points to the same number than the first pointer.

15 ???
Compare search_value with the item in the middle of the list

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binary search

Only applies to ordered lists

Schematic representation of a list containing ordered numbers. The middle pointer has been moved and points to the same number than the first and last pointers.

15 ???
Compare search_value with the item in the middle of the list

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binary search

Only applies to ordered lists

Schematic representation of a list containing ordered numbers. The first, last, and middle pointers points at the same number, 15, that is going to be compared with number 15.

15 ???
Compare search_value with the item in the middle of the list

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binary search

Only applies to ordered lists

Schematic representation of a list containing ordered numbers. The number 15 is circled.

15 ???
Compare search_value with the item in the middle of the list

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

  return False

Binary search - complexity

Complexity: $O(\log{}n)$

Graphical representation of linear search and binary search.

Let's practice!

Data Structures and Algorithms in Python