题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例：
输入: nums = [1,3,5,6], target = 5
输出: 2

题目分析

二分查找，注意不存在时，根据大小来确定预期插入位置：mid 或 mid + 1

Java

public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    int mid = 0;
    while (left <= right) {
        mid = (left + right) >> 1;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    if (target > nums[mid]) {
        return mid + 1;
    } else {
        return mid;
    }
}

Kotlin

fun searchInsert(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    var mid = 0
    while (left <= right) {
        mid = (left + right) / 2
        if (nums[mid] > target) {
            right = mid - 1
        } else if (nums[mid] < target) {
            left = mid + 1
        } else {
            return mid
        }
    }
    return if (target < nums[mid]) mid else mid + 1
}