Recursive & Iterative Binary Search in Scala

Scala

My very first program in Scala. And I don't find Scala close to Java. I am quite used to Java and C++ and rather find the two more close as very as programming is concerned.

Scala however is closer to Java since scala code is converted to Java Bytecode and the executed.

Program

I used 2 classes a Binary Search class & a Tester object

. An object is more like a singleton class according to my understanding. 

The BinarySearch class has constructor which accepts a sorted array.

It has 2 functions 

1. A Recursive Binary Search
2. An Iterative Binary Search.

New To Scala

If you are new to scala, like me. Here's what you need to note

• Similarities between Scala & Java
• Semicolon is optional in Scala
• Function Definition
• Variable Declaration & Definition
• Object vs Class
• mkstring function(used in the program)
• scala.io.StdIn vs Console(deprecated)
• For loop syntax

Code

class BinSearch(nos:Array[Int]){
 var this.nos = nos;

 //recursive binary search
 def rsearch(key:Int,l:Int = 0, r:Int = nos.length-1):Int ={
  if(l>r) {return -1;}
  var mid:Int =(l+r)/2;
  if(nos(mid)== key) return mid;
  if(nos(mid)>key) return rsearch(key,l,mid-1);
  else return rsearch(key,mid+1,r);
 }

 //iterative binary search
 def isearch(key:Int):Int ={
  var l=0;
  var r=nos.length-1;

  while(r>l){
   var mid:Int = (l+r)/2;
   if (nos(mid)==key) return mid;
   else if (nos(mid)<key) l=mid+1;
   else r=mid-1;
  }
  return -1;
  
 }

 



}

object Tester{

 def main(args:Array[String]){
  println("Driver program for Binary Search");
  println("Enter the number of elements in the array");
  var n = scala.io.StdIn.readInt;
  var nos = new Array[Int](n);
  println("Enter the " +n+ " numbers");
  for (i <- 0 to n-1 ){
   println("Enter number "+(i+1));
   nos(i)=scala.io.StdIn.readInt;
  }
  println("The numbers entered are as follows")
  println(nos.mkString(" "))
  println("The numbers after sorting are")
  nos=nos.sorted
  println(nos.mkString(" "))
  var a = new BinSearch(nos)
  println("Enter the key which is to be found")
  println(a.rsearch(scala.io.StdIn.readInt))
  println(a.isearch(scala.io.StdIn.readInt))
 }
}

Execution & Output

Note: You need to install Scala packages before running this program.Since scala doesn't come installed by default. It might be available in your repository for your linux distro.

• For Manjaro Linux

sudo pacman -S scala

[duke@duke-pc]$ scalac bin.scala 

[duke@duke-pc]$ scala Tester

Driver program for Binary Search

Enter the number of elements in the array

6

Enter the 6 numbers

Enter number 1

2

Enter number 2

6

Enter number 3

89

Enter number 4

87

Enter number 5

456

Enter number 6

22

The numbers entered are as follows

2 6 89 87 456 22

The numbers after sorting are

2 6 22 87 89 456

Enter the key which is to be found

22

2

22

2

[duke@duke-pc]$