Abstract

• Search Algorithm
• Divide data into half when searching
  • Time efficient compared to searching one by one progressively
• Think of Up Or Down game
• Time complexity: $O(logN)$
  • Data need to be organized before application

Algorithm

# a = input, x = target value
def binary_search(a, x):
	# set start and end to initial scope of search
	start = 0
	end = len(a) - 1
	# searching loop
	while start <= end:
		mid = (start + end) // 2   # half point
		if x == a[mid]:            # found!
			return mid
		elif x > a[mid]:           # if target is larger, shrink scope to the right
			start = mid + 1
		else                       # if target is smaller, shrink scope to the right
			end = mid - 1
	return -1

# recursive algorithm
def binary_search(arr, start, end, target):
	# calculate mid index and store value
	mid = (start + end) // 2
	mid_value = arr[mid]

	if target == mid_value:   # found!!
		return mid
	elif mid_value > target:  # target value smaller than mid, adjust scope and call
		end = mid - 1
		binary_search(arr, start, end, target)
	elif mid_value < target:  # target value larger than mid value, adjust scope and call
		start = mid + 1
		binary_search(arr, start, end, target)
	else:
		return -1

• Can be written in looping and recursive way
• Main algorithm:
  1. calculate mid index and fetch mid value
  2. compare target value to mid value
     • If found return!
  3. adjust scope and repeat

Problems

• immigration
• Stepping Stones