Searching (un)sorted array

Sequential search

When searching unsorted array for some element, only what we can do is sequential search, which we take elements in the array one by one and check if it's the one we are searching for.

In [ ]:

object SequentialSearch {
  def search[T](array: Array[T], target: T)(implicit ordering: Ordering[T]): Boolean = {
    for (element <- array) {
      if (ordering.compare(target, element) == 0) return true
    }
    false
  }
}

Binary search

When the array containing elements is sorted, we can do much more efficient search than sequential search. Binary search takes the middle element in the array, and if it is bigger than the element we want to find, then search the former half of the array. If it is smaller, then search the latter half.

In [ ]:

object BinarySearch {
  // We assume input array is sorted!
  def search[T](array: Array[T], target: T)(implicit ordering: Ordering[T]): Boolean = {
    var low = 0
    var high = array.length - 1
    while(low <= high) {
      val mid = (low + high) / 2
      val comp = ordering.compare(target, array(mid))
      if (comp < 0) high = mid - 1
      else if (comp > 0) low = mid + 1
      else {
        return true
      }
    }
    false
  }
}

Peak finding problem

1-D

Binary search not only be applied to searching sorted array. Here we consider how to find the i-th element in an array such that $a_{i-1} \leq a_i$ and $a_i \geq a_{i+1}$

In [ ]:

object OneDPeak {
  def searchPeak[T](array: Array[T])(implicit ordering: Ordering[T]): Int = {
    var low = 0
    var high = array.length - 1
    while(low <= high - 2) {
      val mid = (low + high) / 2
      val compLeft = ordering.compare(array(mid), array(mid - 1))
      val compRight = ordering.compare(array(mid), array(mid + 1))
      if (compLeft < 0) high = mid - 1
      else if (compRight < 0) low = mid + 1
      else return mid
    }

    // If the program reaches here, elements to be searched are only low and high
    if (ordering.compare(array(low), array(high)) > 0) low
    else high
  }
}

2-D

2-D version of the algorithm is not a straightforward binary search. It have to take following steps.

Pick the middle column.
Find the global maximum element in the column.
If it is the peak, end search.
If not, limit the search range to the left half if the element to the left is bigger, or limit to the right half it the element to the right is smaller.
return to 1.

The correctness of the algorithm can be shown with proof by contradiction.

Let the width and the height of the 2-D array be m and n. Since step 2 takes $\Theta(n)$ time and the steps repeat $\Theta(\log m)$ time in the worst cases, the time complexity of the algorithm for the worst cases is $\Theta(n\log m)$.

In [ ]:

object TwoDPeak {
  def searchPeak[T](matrix: Array[Array[T]])(implicit ordering: Ordering[T]): (Int, Int) = {
    var low = 0
    var high = matrix.length - 1
    while (low <= high - 2) {
      val mid = (low + high) / 2
      val array = matrix(mid)
      val maxIndex = array.indexOf(array.max)
      val compAbove = ordering.compare(array(maxIndex), matrix(mid - 1)(maxIndex))
      val compBelow = ordering.compare(array(maxIndex), matrix(mid + 1)(maxIndex))
      if (compAbove < 0) high = mid - 1
      else if (compBelow < 0) low = mid + 1
      else return (mid, maxIndex)
    }

    if (low == high) (low, matrix(low).indexOf(matrix(low).max))
    else {
      val maxLow = matrix(low).indexOf(matrix(low).max)
      if (ordering.compare(matrix(low)(maxLow), matrix(high)(maxLow)) >= 0)
        return (low, maxLow)
      (high, matrix(high).indexOf(matrix(high).max))
    }
  }
}

Yuta Nishino

Other articles

Partition-Based Sorting

Sorting based on partition of an array

Shellsort

Transposition Sorting

Sorting by transposition

Stacks and imitating recursion

Stacks