#include<iostream>

using namespace std;

int search(int A[], int n, int key) { // A linear search strategy
 // If key is in the array A returns the index of occurrence.
   int i= 0;
   while (i<n && A[i]!=key) {
    i++;
   }
   return i;
}

int binarySearch (int A[], int l, int r, int key)  // A binary search strategy
{ // If key is in the array A[l..r], returns the index of occurrence.
   if (l+1 < r) {
     int mid= (l+r)/2;
     if (A[mid] <= key) return binarySearch(A, mid, r, key);
     else return binarySearch(A, l, mid-1, key);
   }
   else {if (A[l] == key) return l;
         else return r;}
}

struct node {
  int item;
  node* next;
};

typedef node* ptr;

void binarySearchLinked(ptr l, ptr r, int key, ptr& found) {
 // PRE: l and r are pointers to the beginning and the end of the sorted list;
 // key is the item to be found
 // POST: found is set to the node in the list between l and r if its item is key,
 //       if no such item exists then found is set to NULL

    // put your code here

}


void insert (ptr& l, int it) {
  // creates a node containing it and inserts it at the head of the list l
}

int main() {

 // Now add code here to compare the performance of binarySearch and binarySearchLinked.  
   

}