Finding Start and End Index of an element in a sorted Array using Kotlin

Finding start and end index of an element in a sorted array using Kotlin programming language will be shown here. The array may contain duplicate elements and we will see how to find a start and end index for an element in this array elements. We may design the algorithm for finding start and end index of an element in a sorted array in various ways but we need to consider also for the optimized solution.

We can simply iterate through array elements and find the start and end index of an element in array but that would not give us the optimal solution. Therefore we will use the existing algorithm Binary Search that will help us finding the start and end index of an element in array optimally. We know the time complexity of Binary Search algorithm: Best Case – O(1) i.e. constant; Average Case – O(logn); Worst Case – O(logn). You can read more about Binary Search using C.

Here we will use Kotlin programming language for finding start and end index of an element in a sorted array. You can also use any programming language to implement the same algorithm.

Let’s move on to the example…

Prerequisites

Knowledge of any programming language
Softwares
Eclipse
JDK
Kotlin dependencies

Implementing the Example

Let’s take an example. We have an array of integers with the following elements in it:

1, 1, 2, 2, 3, 3, 3, 3, 3, 5, 8, 6, 9

Now say, we want to find the start and end index of element 3 then it is obvious that start index of element 3 will be 4 and end index will be at 8 on a 0 based index array.

Now we will be finding start and end index of an element in a sorted array using Kotlin. Here we will use the same array elements as shown in the above example.

Let’s move on to the code implementation part…

Here in the below source code we have used the Binary Search algorithm to find the start or end index. We have created a Kotlin class ArrayOperation and put two separate recursive methods for finding the indices. Then from the main method we are calling those two methods to find the indices of the element in the array.

package com.roytuts.algo
fun main(args: Array<String>) {
   val arr = intArrayOf(1, 1, 2, 2, 3, 3, 3, 3, 3, 5, 8, 6, 9);
   val totalElements = arr.size;
   val startIndex = ArrayOperation().findStartIndex(arr, 0, totalElements, 3);
   val endIndex = ArrayOperation().findEndIndex(arr, 0, totalElements, 3, totalElements);
   println("Start Index: " + startIndex + ", End Index: " + endIndex);
}
class ArrayOperation {
   fun findStartIndex(arr: IntArray, low: Int, high: Int, x: Int): Int {
	  if (high > low) {
			 var mid = low + (high - low) / 2;
			 if ((mid == 0 || x > arr[mid - 1]) && x == arr[mid]) {
				   return mid;
			 } else if (x > arr[mid]) {
				   return findStartIndex(arr, mid + 1, high, x);
			 } else {
				   return findStartIndex(arr, low, mid - 1, x);
			 }
	  }
	  return -1;
   }
   fun findEndIndex(arr: IntArray, low: Int, high: Int, x: Int, totalElements: Int): Int {
	  if (high > low) {
			 var mid = low + (high - low) / 2;
			 if ((mid == totalElements - 1 || x < arr[mid + 1]) && x == arr[mid]) {
				   return mid;
			 } else if (x < arr[mid]) {
				   return findEndIndex(arr, low, mid - 1, x, totalElements);
			 } else {
				   return findEndIndex(arr, mid + 1, high, x, totalElements);
			 }
	  }
	  return -1;
   }
}

Running the Kotlin class

Run the above class by doing right-click on the Hello.kt file and Run As -> Kotlin Application. You will see below output in the console.

Start Index: 4, End Index: 8

Thanks for reading.

Leave a Reply

Your email address will not be published. Required fields are marked *