Welcome to CS1315. Click on the python to add comments. Looking for the book? They have it at the Engineer's Bookstore at 748 Marietta St NW. Here is there website: http://www.engrbookstore.com/ - Monica
	Hotspots: Slides and Code • TA Corner • Comments? • Announcements • FAQ • Static Webspace

finding a needle (a number) in a haystack (a list)

def linearSearch(needle, haystack):
  comparisons = 1
  for element in haystack:
    printNow(str(comparisons))
    if element == needle:
      return 0
    comparisons += 1
  return 0

def binarySearch(needle, haystack):
  low = 1
  high = len(haystack) - 1
  comparisons = 1
  while (low <= high):
    middle = int((low+high)/2.0)
    printNow(str(comparisons)+":Checking at: "+str(middle)+" low="+str(low)+" high="+str(high))
    if haystack[middle]==needle:
      return 1
    if haystack[middle]<needle:
      low = middle+1
    if haystack[middle]>needle:
      high = middle-1
    comparisons += 1
  return 0

Link to this Page

• Slides and Code- Spring 2008 last edited on 23 April 2008 at 11:00 am by lawn-128-61-23-153.lawn.gatech.edu