# Important algorithms to know:

# Binary Search 
def binsearch(x,A):   # A must be sorted in increasing order
  answer = False
  min,max = 0,len(A)-1
  while answer==False and min<=max:
     mid = (min+max)//2
     if A[mid]==x: answer = True
     elif A[mid]>x: max = mid-1
     else: min = mid+1
  #while
  return answer
#binsearch


# swapsort: sort list A (in increasing order) by swaping the ith smallest
# value to A[i].

def swapsort(A):
  i = 0
  while i<=len(A)-2:
    # find index of smallest value starting at index i:
    si = i  # index of smallest
    k = i+1
    while k<=len(A)-1:
      if A[k]<A[si]: si=k
      k +=1
    # while k
    A[i],A[si] = A[si],A[i] # swap ith smallest to A[i]
    i += 1
  # while i
#swapsort

## note: changing A[i] is not the same as changing A: the effect of
# changing A[i] is carried externally to the function.  This has to do
# with the fact that arrays are mutable structures.


## Randomly permuting an array:
from random import randint
def randperm(P):
   i = 0
   while i<=len(P)-2:
       k = randint(i,len(P)-1)
       P[i],P[k] = P[k],P[i]
       i += 1
   # while
#randperm