Question 1: You are a contestant on the hit game show "Beat Your Neighbors!" You are presented with an length n array of boxes, each containing a unique number. It costs $100 to open a box. Your goal is to find a box whose number is larger than its neighbors in the array (left and right). Describe an O(log n) algorithm that finds a number that is bigger than either of its neighbors.

Question 2 -You are given an n x n matrix represented as a 2-dimensional array A[1::n][1::n] (there are totally n 2 elements). Each row of A is sorted in increasing order and each column is sorted in increasing order. Your goal is to find whether some given element x is in A or not. Note that you can do only comparisons between elements (no hash table, or any other set data structures). Give an algorithm that takes O(n) comparisons. [Hint: try to start on one some corner, and eliminate one row/column per move].

Please explain in detail. Don't need the actual code just pseudo code will work but please give a detail explanation. Thanks!