Scala program to find the rotation point in a rotated sorted array

1. Introduction

A "rotated sorted array" refers to an initially sorted array that has been rotated some number of times. For instance, an array [1, 2, 3, 4, 5] rotated twice becomes [3, 4, 5, 1, 2]. The "rotation point" is the index where the smallest element resides. Identifying this point efficiently is crucial in various search algorithms. In this tutorial, we will implement a Scala program that finds the rotation point in a rotated sorted array using a binary search approach.

2. Program Steps

1. Initialize the Scala environment.

2. Declare the rotated sorted array.

3. Implement a function to determine the rotation point using binary search.

4. Print the index of the rotation point.

5. Execute the program.

3. Code Program

object RotationPointApp {
  def main(args: Array[String]): Unit = {
    // Sample rotated sorted array
    val rotatedArray = Array(3, 4, 5, 1, 2)

    // Find the rotation point of the array
    val rotationPointIndex = findRotationPoint(rotatedArray)

    println(s"The rotation point is at index: $rotationPointIndex")
  }

  def findRotationPoint(arr: Array[Int]): Int = {
    var low = 0
    var high = arr.length - 1
    while (low < high) {
      val mid = (low + high) / 2
      if (arr(mid) > arr(high)) {
        low = mid + 1
      } else {
        high = mid
      }
    }
    low
  }
}

Output:

The rotation point is at index: 3

Explanation:

1. Our program is contained within the RotationPointApp object.

2. Inside the main function, we declare our sample rotated sorted array, rotatedArray.

3. We implement the findRotationPoint function, which uses binary search to efficiently find the rotation point in the array. The idea is to continually narrow down the search range until the rotation point is found.

4. When the arr(mid) > arr(high), it implies the rotation point is to the right of mid. Otherwise, it's to the left or at mid itself.

5. We then call our function and print the result. The given sample array, once rotated, puts the smallest number (1) at the 3rd index, thus the output.