# Chapter 03: Algorithms¶

## Example 03: Page 195¶

In :
def binarysearch(a,num): #function definition with its parameters 'a' is the inputlist
#and 'num' number to be found

first=0 #initially the first position is zero
last=len(a)-1 #initially the last position is the total length of the inputlist-1
found=False #boolean value to indicate if the number to be searched is found or not.

midpoint=(first+last)//2 #dividing the inputlist into two halves and comparing the number to be found with the midpoint.

if a[midpoint]==num: #If the number to be found is equal to the midpoint returns the position.
found=True
else:
if num<a[midpoint]: #if the number to be found is less than the midpoint
#then the first half of the divided input list is taken for further computation.

last=midpoint-1 #by assigning the last number of the first half(number before the midpoint) to the variable last.

else:
first=midpoint+1 #if the number to be found is greater than the midpoint
#then the second half of the divided input list is taken for further computation.
#by assigning the first number of the second half(number following the midpoint) to the variable first.

return midpoint #returns the position of the number found in the list.

numlist=[1, 23, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22] #List of inputs
print "Found number 19 at the position",(binarysearch(numlist, 19)) #Printing the position of the number to be found by a function call.
#The function binarysearch is called along with its parameters, inputlist
#and the number to be found.

Found number 19 at the position 12


## Example 05: Page 198¶

In :
#To perform insertionsort
def sort_insertion(inputlist):

for i in range(1,len(inputlist)):

val_current = inputlist[i]
pos = i

# check backwards through sorted list for proper pos of val_current
while((pos > 0) and (inputlist[pos-1] > val_current)):
inputlist[pos] = inputlist[pos-1]
pos = pos-1

if pos != i:
inputlist[pos] = val_current
print(inputlist)
return inputlist
inputlist = [3,2,4,1,5]
print sort_insertion(inputlist)

[2, 3, 4, 1, 5]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]