Tag Archives: Binary search algorithm

Search in 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

Well I guess anyone knows binary search can think of a straightforward solution: just think of this matrix as a long array with m*n elements and apply binary search on it. So it takes O(logmn) = O(logm) + O(logn) But we should probably ask: is m*n still in the range of Integer in Java? If true, good. Go ahead.

If not, and if m and n are in the range of Integer in Java, we could do it in another way: use two passes of binary search, one to locate the possible row that the target could reside in, and the other to search the target on that row. But this one is a bit tricky and be sure to check boundary cases.

Code on github:

Enhanced by Zemanta

Search in a bitonic array

Q: Search in a bitonic array. An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct integer values, determines whether a given integer is in the array.

  • Standard version: Use ∼3lgN compares in the worst case.
  • Signing bonus: Use ∼2lgN compares in the worst case (and prove that no algorithm can guarantee to perform fewer than ∼2lgN compares in the worst case).

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

Well, we could just go for linear search but that takes O(N) time. The question requires O(lgN). The only search with O(N) time I know is binary search, which requires a sorted array. We have a bitonic array. Well in some sense it consists of two sorted parts with a turning point in between. For example:

1, 2, 4, 7, 10, 9, 5, 3, 0

So if I know where the turning point is, I could just apply binary search on both sorted parts. That takes 2lgN. How do we find the turning point? Again, we could use linear search with O(N) time, but then there’s no point of doing any of these things above. The standard version is 3lgN. We used 2lgN, so I guess finding the turning point uses the left lgN time, with a binary search.

But how do we apply binary search to find the turning point? Think about the characteristics of a turning point. Say we look at the element at index I:

  1. If  A[I-1] < A[I] < A[I+1], A[I] is not the turning point and we are stilling in the ascending sequence;
  2. If A[I-1] > A[I] > A[I+1], A[I] is not the turning point and we are in the descending sequence;
  3. If A[I-1] < A[I] > A[I+1], then A[I] is the turning point.

Then we can apply binary search on it and instead of looking for a specific element, we look for the element with the 3rd characteristic. In this way, we can find the turning point and the rest is easy.

As for the 2lgN, I’m still working on it…Probably I have to eliminate one binary search here, but which one and how?

Code on github:

Enhanced by Zemanta