Kotlin 数组 - binarySearch() 函数

---

---

Kotlin 数组的 binarySearch() 函数用于使用二分查找算法在数组中搜索给定元素。

数组应根据其元素的可比自然顺序（比较器）排序；否则，结果未定义。

此函数的例外情况如下：

• IndexOutOfBoundsException：如果 fromIndex 小于零或 toIndex 大于此数组的大小。
• IllegalArgumentException：如果 fromIndex 大于 toIndex。

如果数组包含多个等于指定元素的元素，则此函数无法保证找到哪个元素。

语法

以下是 Kotlin 数组 binarySearch() 函数的语法：

fun <T> Array<out T>.binarySearch(
   element: T,
   comparator: Comparator<in T>,
   fromIndex: Int = 0,
   toIndex: Int = size
): Int

参数

此函数接受以下参数：

• element：要搜索的元素。

• comparator：根据此数组排序的比较器。

• fromIndex：表示搜索范围的起始位置（包含），默认为 0。

• toIndex：表示搜索范围的结束位置（不包含），默认为此数组的大小。

返回值

如果元素包含在指定范围内的数组中，则此函数返回元素的索引；否则，返回反向插入点 (-插入点 - 1)。

插入点是应插入元素的索引。

示例 1

以下是一个基本示例，用于演示 binarySearch() 函数的使用：

fun main(args: Array<String>) {
   val numbers: Array<Int> = arrayOf(1, 2, 3, 4, 5)
   val index = numbers.binarySearch(2)
   println("Element fount at index: $index")
}

输出

以下是输出：

Element fount at index: 1

示例 2

现在，让我们看另一个示例。我们创建一个大小为 8 的数组，该数组按升序排序。然后，我们使用 binarySearch() 函数查找特定元素的索引：

fun main(args: Array<String>) {
   // Create a sorted array
   val numbers = arrayOf(1, 3, 5, 7, 9, 11, 13, 15)

   val searchElement = 7

   // use the binarySearch()
   val index = numbers.binarySearch(searchElement)

   if (index >= 0) {
      println("Element $searchElement found at index $index")
   } else {
      println("Element $searchElement not found. Insertion point: ${-index - 1}")
   }
}

输出

以下是输出：

Element 7 found at index 3

示例 3

下面的示例创建一个大小为 5 的整数数组，该数组未按排序顺序排列。然后，我们使用 binarySearch() 来查看是否获得了元素的索引：

fun main() {
   // create an unsorted array
   val numbers = arrayOf(3, 1, 7, 5, 9)
   val searchElement = 7
   
   // Check if the array is sorted
   if (isSorted(numbers)) {
      //use the binarySearch()
      val index = numbers.binarySearch(searchElement)
      if (index >= 0) {
         println("Element $searchElement found at index $index")
      } else {
         println("Element $searchElement not found. Insertion point: ${-index - 1}")
      }
   } else {
       println("Undefined: The array is not sorted.")
   }
}
fun isSorted(array: Array<Int>): Boolean {
   for (i in 0 until array.size - 1) {
      if (array[i] > array[i + 1]) {
         return false
      }
   }
   return true
}

输出

以下是输出：

Undefined: The array is not sorted.

示例 4

下面的示例显示，如果数组中不存在元素，则会抛出“IndexOutOfBoundsException”：

fun main() {
   val numbers = arrayOf(1, 3, 5, 7, 9, 11, 13, 15)

   try { 
      // Perform a binary search for an element not in the array
      val invalidIndex = numbers.binarySearch(20)
      
      // This will throw IndexOutOfBoundsException because the index is negative
      println("Element at invalid index $invalidIndex: ${numbers[invalidIndex]}")
   } catch (e: IndexOutOfBoundsException) {
      println("IndexOutOfBoundsException caught: ${e.message}")
   }
}

输出

以下是输出：

IndexOutOfBoundsException caught: Index -9 out of bounds for length 8