leetcode/array/1binary search/35search-insert-position/kotlin/Solution.kt

/**
 * LeetCode 解题模板
 * 
 * 使用方法：
 * 1. 在 Solution 类中实现你的算法
 * 2. 在 main 函数中添加测试用例
 * 3. 运行：kotlinc Solution.kt -include-runtime -d Solution.jar && java -jar Solution.jar
 *    或者使用 IDE（如 IntelliJ IDEA）直接运行
 */

/**
 * 示例：搜索插入位置
 * 
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
 * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 
 * 请必须使用时间复杂度为 O(log n) 的算法。
 */
class Solution {
    /**
     * 搜索插入位置
     * 
     * @param nums 排序数组
     * @param target 目标值
     * @return 目标值的索引，如果不存在则返回插入位置
     */
    fun searchInsert(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size - 1
        
        while (left <= right) {
            val mid = left + (right - left) / 2
            when {
                nums[mid] == target -> return mid
                nums[mid] < target -> left = mid + 1
                else -> right = mid - 1
            }
        }
        
        return left
    }
}

/**
 * 打印测试结果
 */
fun printTestResult(testName: String, passed: Boolean) {
    val status = if (passed) "pass" else "fail"
    println("$testName: $status")
}

/**
 * 比较两个整数是否相等
 */
fun assertEquals(actual: Int, expected: Int): Boolean {
    return actual == expected
}

fun main() {
    val solution = Solution()
    
    // 测试用例 1: 目标值存在于数组中
    val nums1 = intArrayOf(1, 3, 5, 6)
    val target1 = 5
    val result1 = solution.searchInsert(nums1, target1)
    val expected1 = 2
    printTestResult("test case 1:target exists $target1", assertEquals(result1, expected1))
    
    // 测试用例 2: 目标值不存在，应插入到中间位置
    val nums2 = intArrayOf(1, 3, 5, 6)
    val target2 = 2
    val result2 = solution.searchInsert(nums2, target2)
    val expected2 = 1
    printTestResult("test case 2:insert in middle $target2", assertEquals(result2, expected2))
    
    // 测试用例 3: 目标值大于所有元素
    val nums3 = intArrayOf(1, 3, 5, 6)
    val target3 = 7
    val result3 = solution.searchInsert(nums3, target3)
    val expected3 = 4
    printTestResult("test case 3:insert at end $target3", assertEquals(result3, expected3))
    
    // 测试用例 4: 目标值小于所有元素

    val nums4 = intArrayOf(1, 3, 5, 6)
    val target4 = 0
    val result4 = solution.searchInsert(nums4, target4)
    val expected4 = 0
    printTestResult("test case 4:insert at start $target4", assertEquals(result4, expected4))

    println("\n all test cases passed!")
}