Lesson 3.11 Binary Search

Goals/Objectives:

  • detirmine number of iterations required to find vlue in data set.
  • explain requirements for binary search

What is Binary Search?

  • Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.
  • An algorithm for iterating to find a value inside a data set

About Binary Search:

  • Binary Search Algorithm starts in the middle of a data set of numbers and eliminates half the data. This process reapeats until the desired value is found or until all elements have been eliminated.
  • In order to use binary search effectivly and properly, data must be stored in order
  • COLLEGE BOARD INDEX STARTS AT 1 NOT 0

Think about how you would you would try to find a certain number in this set.

One way would be to line up the numbers and count them individually untill you find the desired value.

When working with large data sets with lots of numbers, methods like these wont work

  • Instead, a Binary Search would be more effective.

Here we can see the numbers are set in an increasing order. Setting numbers in an increasing or decreasing is needed for a binary search

  • Binary search is started with the middle number first
    • Middle number is found by taking the higest index number plus the lowest and divided by two
  • Binary Search can be represented using a tree as shown below

Heres an easy way to put it:

  • binary search fidns the desired element by continuously chopping the search area in half
  • say the element you are looking for is 'f'

[a b c d e f g h]

  • We would start in the middle at element 'd'

  • becuase our target is greater than d we will eliminate everything left of 'd' including 'd' (chopping it in half)

    [e f g h] is what now remains

    • again we would 'chop in half'
    • say we iterate through 'g' and 'h', our desired element is still not found so we would eliminate 'g; and 'h' and continue the process

    [e f]

    • now we are down to 2 elements
    • 'chopping in half' will give us our desired element

    [f]

def binarySearch(array, x, low, high):

    # Repeat until the pointers low and high meet each other
    while low <= high:

        mid = low + (high - low)//2

        if array[mid] == x:
            return mid

        elif array[mid] < x:
            low = mid + 1

        else:
            high = mid - 1

    return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

Element is present at index 1

Hacks

Using my example above and steps below, create your own iteration using binary search

Steps

  • Compare x with the middle element.
  • If x matches with the middle element, we return the mid index.
  • Else if x is greater than the mid element, then x can only lie in the right (greater) half subarray after the mid element. Then we apply the algorithm again for the right half.
  • Else if x is smaller, the target x must lie in the left (lower) half. So we apply the algorithm for the left half.