Problem 1:

Binary search will examine at most log(N) elements to perform a search a list
of size N. Sequential search examines at most N elements, considerably more
than binary search in the worst case.

Problem 2:

a) linear: O(n)
b) linear: O(n)
c) linear: O(n^2)
d) linear: O(n)

Problem 3:

public static boolean binarySearch(int[] haystack, int needle) {
   int low = 0;
   int high = haystack.length;
   while (low + 1 < high) {
      int mid = (low + high) / 2;
      if (needle < haystack[mid])
         high = mid;
      else
         low = mid;
   }
   return haystack[low] == needle;
}

public boolean sequentialSearch(int[] haystack, int needle) {
   for (int i = 0; i < haystack.length; i++)
      if (haystack[i] == needle)
         return true;
   return false;
}