Scala中的二进制搜索
搜索是已在高级概念中找到应用程序的编程中的重要概念之一。有很多算法可以从数组中搜索元素。
在这里，我们将学习Scala中的二进制搜索算法。
二元搜寻
这是一种搜索算法，用于在排序后的数组中查找元素。二进制搜索的时间复杂度为O(logn)。二分查找的工作原理是分而治之。并且需要将数组排序为用于搜索元素的数组。
在二进制搜索算法中，我们采用数组的中间元素。并在此位置搜索所需的元素。比较数组的中间元素和searchElement会出现三种情况。
情况1：如果（中间元素==searchElement），则返回元素的索引。
情况2：如果（middleelement<searchElement），我们将在子数组中搜索元素，该元素从中间索引值之后的索引开始，到数组的最后一个索引结束。
情况3：如果（middleelement>searchElement），我们将在子数组中搜索从第一个索引开始并在小于中间索引的索引处结束的元素。
排序算法将继续进行，直到找到元素或创建的子数组的大小变为0。
显示二进制搜索如何工作的示例，
Array = {1, 4, 9, 10, 16, 22, 26, 29, 32, 36}
searchElement = 4
size = 10
Iteration 1:
start = 0, end = 9,
mid = (start + end)/2 = (0 + 9)/2 = 4.
Element at index 4 is 16.
Element 16 > 4. Update end to (4-1) = 3.
Iteration 2:
start = 0, end = 3,
mid = (start + end)/2 = (0 + 3)/2 = 1.
Element at index 1 is 4.
Element at 4 == 4. Element found at index 1.二进制搜索可以使用递归方法或迭代方法来实现。
递归方法
在递归方法中，我们将创建一个将为每个子数组调用的函数。
程序：
object BinarySearch{
def BinarySearchRec(arr: Array[Int], Element_to_Search: Int, start: Int, end: Int): Int =
{
if (start > end)
return -1
var mid = start + (end - start) / 2
if (arr(mid) == Element_to_Search)
return mid
else if (arr(mid) > Element_to_Search)
return BinarySearchRec(arr, Element_to_Search, start, (mid-1))
else
return BinarySearchRec(arr, Element_to_Search, (mid+1), end)
}
def main(args: Array[String]){
val searchElement = 4
val sortedArray = Array(1, 4, 9, 10, 16, 22, 26, 29, 32, 36)
var elementIndex = BinarySearchRec(sortedArray, searchElement, 0, 6);
if(elementIndex == -1)
print("Not Found")
else
print("Element found at index value " + elementIndex)
}
}输出：
Element found at index value 1
在这里，我们创建了一个数组sortedArray和searchElement，这是要搜索的元素。为了找到元素的索引，我们将使用二进制搜索并使用递归方法来实现它。该函数根据searchElement与当前数组的mid元素的比较值，使用不同的子数组调用自身。