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