Find the First And Last Index of the element in Sorted Array in Kotlin

by

To find the first and last index of the same element in a sorted array, we can use a modified binary search algorithm. Here are the steps:

  1. Initialize two variables, firstIndex and lastIndex, to null.
  2. Set low and high to be the first and last indices of the array, respectively.
  3. While low is less than or equal to high, do the following:
    • Set mid to be the middle index of the array, rounded down.
    • If the element at mid is the same as the element we are looking for, set firstIndex to mid and update high to search for the first occurrence of the element to the left of mid.
    • If the element at mid is less than the element we are looking for, update low to search to the right of mid.
    • If the element at mid is greater than the element we are looking for, update high to search to the left of mid.
  4. Reset low and high to be the first and last indices of the array, respectively.
  5. While low is less than or equal to high, do the following:
    • Set mid to be the middle index of the array, rounded down.
    • If the element at mid is the same as the element we are looking for, set lastIndex to mid and update low to search for the last occurrence of the element to the right of mid.
    • If the element at mid is less than the element we are looking for, update low to search to the right of mid.
    • If the element at mid is greater than the element we are looking for, update high to search to the left of mid.
  6. If both firstIndex and lastIndex are not null, we have found the first and last indices of the element we are looking for in the array. Return a pair of firstIndex and lastIndex.
  7. If either firstIndex or lastIndex is null, the element we are looking for is not in the array. Return a pair of null values.

The time complexity of this algorithm is O(log n), where n is the number of elements in the array, since we are performing a binary search twice.

Kotlin
fun findFirstAndLastIndex(arr: IntArray, element: Int): Pair<Int?, Int?> {
    var firstIndex: Int? = null
    var lastIndex: Int? = null
    // Find first index
    var low = 0
    var high = arr.size - 1
    while (low <= high) {
        val mid = low + (high - low) / 2
        if (arr[mid] == element) {
            firstIndex = mid
            high = mid - 1
        } else if (arr[mid] < element) {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    // Find last index
    low = 0
    high = arr.size - 1
    while (low <= high) {
        val mid = low + (high - low) / 2
        if (arr[mid] == element) {
            lastIndex = mid
            low = mid + 1
        } else if (arr[mid] < element) {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return Pair(firstIndex, lastIndex)
}
fun main() {
    val arr = intArrayOf(1, 2, 3, 3, 3, 4, 4, 5, 6)
    val element = 3
    val indices = findFirstAndLastIndex(arr, element)
    if (indices.first != null && indices.second != null) {
        println("The first index of $element is ${indices.first} and the last index is ${indices.second}.")
    } else {
        println("$element is not in the array.")
    }
}

The function takes two arguments: an integer array arr and an integer element. The goal of the function is to find the first and last indices of the element in the arr array, assuming that the array is sorted in ascending order.

The function first initializes two variables firstIndex and lastIndex to null, which will be used to store the first and last indices of the element in the array, respectively.

Next, the function uses a modified binary search algorithm to find the first index of the element in the array. The binary search algorithm works by dividing the array in half repeatedly until the target element is found or until the search range is exhausted. The algorithm maintains two indices, low and high, which represent the lower and upper bounds of the search range, respectively.

In this case, the binary search algorithm is modified slightly to find the first index of the element. Whenever the algorithm finds an element that matches the target, it updates firstIndex to the current index and then continues searching the left half of the array. This ensures that firstIndex will always be updated with the leftmost occurrence of the element in the array.

Similarly, the function uses another binary search algorithm to find the last index of the element in the array. This time, whenever the algorithm finds an element that matches the target, it updates lastIndex to the current index and then continues searching the right half of the array. This ensures that lastIndex will always be updated with the rightmost occurrence of the element in the array.

Once both binary search algorithms have completed, the function returns a Pair containing the values of firstIndex and lastIndex.

In the main function, we create an example array and element to search for, and call the findFirstAndLastIndex function with these values. If the firstIndex and lastIndex are not null, we print the indices to the console, along with the value of the target element. If either of the indices are null, we print a message indicating that the target element was not found in the array.

Leave a Comment