Binary Search Algorithm in Scala

1. Introduction

Binary Search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one. 

The key idea behind Binary Search is that it reduces the problem size by half with each step, leading to a time complexity of O(log n).

2. Implementation Steps

1. Initialize two pointers: low at the beginning and high at the end of the list.

2. Calculate the middle index mid as the average of low and high.

3. If the element at index mid is the target, return mid.

4. If the element at mid is less than the target, set low to mid + 1 and repeat step 2.

5. If the element at mid is greater than the target, set high to mid - 1 and repeat step 2.

6. If low exceeds high, the target is not in the list, and the search should be terminated.

3. Implementation in Scala

object BinarySearch {
  def search(arr: Array[Int], x: Int): Int = {
    var low = 0
    var high = arr.length - 1
    while (low <= high) {
      val mid = (low + high) / 2
      arr(mid) match {
        case e if e == x => return mid
        case e if e < x => low = mid + 1
        case _ => high = mid - 1
      }
    }
    -1  // return -1 if the element is not found
  }
}
// Client code to test the binary search algorithm
val array = Array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val target = 7
val result = BinarySearch.search(array, target)
if (result != -1) println(s"Element $target is present at index $result")
else println(s"Element $target is not present in the array")

Output:

Element 7 is present at index 6

Explanation:

1. The search function begins with the entire list as the range where the target might be.

2. It calculates the middle index mid and checks the element at that index.

3. Based on the value at the middle index, the function determines whether the target lies to the left or the right of mid.

4. If the value at mid is equal to the target, the index is returned.

5. If the value at mid is less than the target, it means the target lies to the right of mid, so the low pointer is moved to mid + 1.

6. If the value at mid is greater than the target, it means the target lies to the left of mid, so the high pointer is moved to mid - 1.

7. This process repeats, halving the search range each time, until the target is found or the range is empty.