Scala : Binary Search

Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.

Binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the subarray reduces to zero.

 

Scala Program as below

 

object binarysearch extends App {

var arr=Array(1,2,13,45,55,61,74)
var mid=arr.length/2
var initial=0
var res=0
var last=arr.length-1

def binarysearch(x:Int):Int=
{
for(i<- initial to last)
{
if(arr(mid)==x)
{
res =arr(mid)

}
else if(x > arr(mid))
{
initial=mid +1
last=arr.length-1
mid = initial + (last – initial)/2

}
else
{
initial=0
last=mid-1
mid = initial + (last – initial)/2
}

}
res
}

println(binarysearch(45))
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s