CITS2200 - Lecture 3

← Back to Home

CITS2200 - Lecture 2
Recursion and Binary Search - Slides

Recursion

• Recursion is when a function/process calls itself
  i.e. it breaks down the problem into smaller, similar subproblems

Example of a recursive program in Python:

def factorial(n):
	if n == 0:
		return 1
	else:
		return n * factorial(n-1)

A recursive function must contain:

• ! A base case $-$ when executed, recursion stops
  • Every possible chain of recursive calls must reach a base case
• ~ Recursive calls $-$ calls to the current method
  • Each recursive call should be defined so that it makes progress towards a base case

Binary Search

• Binary search is an algorithm that finds the position of a target value in a sorted array by repeatedly dividing the search interval in half
  • It is more efficient compared to checking each value in the array

• Binary search only works when data is comparable
  e.g. comparing the size of integers

Example binary search function:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
 
    while low <= high:
        mid = (low + high) // 2   # middle index
 
        if arr[mid] == target:
            return mid            # target found
        elif arr[mid] < target:
            low = mid + 1         # search right half
        else:
            high = mid - 1        # search left half
 
    return -1                     # target not found

Binary search runs in $O(\log n)$ time → at most there can be $\log n$ levels

• The array is divided in half each step
• Worst case scenario takes only $\log n$ steps
  The algorithm gets slower very slowly as the array size increases

---

CITS2200 - Lecture 4