My algorithm should search Binary but i dont why it doenst work

Question

My binarySearch algorithm doesnt work. Can you help me ?

It should find target value from the given sorted array values. If the value could not be found, return None

def binarySearch(values: Array[Int], target: Int): Option[Int] = {
    val n = values.size
    var left = 0
    var right = n - 1
    while(left <= right){
      val mid = (left + right) / 2
      val value = values(mid)
      if(value == target)
        return Some(mid)
      else if(value < target)
        right = mid
      else
        left = mid
    }
    None
  }

Answer 1

Your code suffers from a number of problems.

First off, the while loop condition, left <= right, is always true. The value of mid = (left+right)/2 can never adjust left or right such that left > right.

There's an easy fix for this: while (left < right). But this unfortunately creates 2 exit results, the target can't be found or the target is the final value, so we need to test for that after exiting the while loop.

if (values(left) == target) Some(left) else None

The next problem is that you're adjusting the wrong variable for current mid value. The simple fix is to change from if(value < target) to if(value > target).

Also, after you know that mid is not the target we're looking for, it doesn't have to be retained for any future grouping. So now that section looks like this:

else if(value > target)
  right = mid-1
else
  left = mid+1

Finally, your code doesn't handle the empty array condition. Let's add that test at the end.

if (n > 0 && values(left) == target) Some(left) else None

So now the code passes all the tests that I've thrown at it. Unfortunately it's still an ugly hodgepodge of mutable variables and imperative programming. Not the clean FP Scala style we like to see.

Here's a possible alternative worth considering.

def binarySearch(values :Array[Int], target :Int) :Option[Int] = {
  def bs(lo :Int, hi :Int) :Option[Int] = {
    val mid = (lo + hi)/2
    target compare values(mid) match {
      case  0             => Some(mid)    //found
      case _ if mid == lo => None         //can't be found
      case -1             => bs(lo, mid)  //lower half
      case  1             => bs(mid, hi)  //upper half
    }
  }
  values.headOption.flatMap(_ => bs(0, values.length))
}

testing:

val arr = Array(1,2,3,5,6)
binarySearch(arr,0)               //res0: Option[Int] = None
binarySearch(arr,1)               //res1: Option[Int] = Some(0)
binarySearch(arr,2)               //res2: Option[Int] = Some(1)
binarySearch(arr,3)               //res3: Option[Int] = Some(2)
binarySearch(arr,4)               //res4: Option[Int] = None
binarySearch(arr,5)               //res5: Option[Int] = Some(3)
binarySearch(arr,6)               //res6: Option[Int] = Some(4)
binarySearch(arr,7)               //res7: Option[Int] = None
binarySearch(Array.empty[Int],8)  //res8: Option[Int] = None