# 1. Introduction

Binary Search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

The key idea behind Binary Search is that it reduces the problem size by half with each step, leading to a time complexity of O(log n).

# 2. Implementation Steps

1. Initialize two pointers: *low* at the beginning and *high* at the end of the list.

2. Calculate the middle index *mid* as the average of *low* and *high*.

3. If the element at index *mid* is the target, return *mid*.

4. If the element at *mid* is less than the target, set *low* to *mid + 1* and repeat step 2.

5. If the element at *mid* is greater than the target, set *high* to *mid - 1* and repeat step 2.

6. If *low* exceeds *high*, the target is not in the list, and the search should be terminated.

# 3. Implementation in Scala

```
object BinarySearch {
def search(arr: Array[Int], x: Int): Int = {
var low = 0
var high = arr.length - 1
while (low <= high) {
val mid = (low + high) / 2
arr(mid) match {
case e if e == x => return mid
case e if e < x => low = mid + 1
case _ => high = mid - 1
}
}
-1 // return -1 if the element is not found
}
}
// Client code to test the binary search algorithm
val array = Array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val target = 7
val result = BinarySearch.search(array, target)
if (result != -1) println(s"Element $target is present at index $result")
else println(s"Element $target is not present in the array")
```

### Output:

Element 7 is present at index 6

### Explanation:

1. The *search* function begins with the entire list as the range where the target might be.

2. It calculates the middle index *mid* and checks the element at that index.

3. Based on the value at the middle index, the function determines whether the target lies to the left or the right of *mid*.

4. If the value at *mid* is equal to the target, the index is returned.

5. If the value at *mid* is less than the target, it means the target lies to the right of *mid*, so the *low* pointer is moved to *mid + 1*.

6. If the value at *mid* is greater than the target, it means the target lies to the left of *mid*, so the *high* pointer is moved to *mid - 1*.

7. This process repeats, halving the search range each time, until the target is found or the range is empty.

## Comments

## Post a Comment