搜索插入位置（简）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

引言

想象一下，你早上起床，迷迷糊糊地开始找袜子。你可能会一只一只地看，这样的方法我们称之为“线性查找”。但如果你是个效率达人，你可能会先看看袜子是厚的还是薄的，然后直接在厚袜子或薄袜子堆里找。这种方法，就是我们今天要聊的“二分查找”。

什么是二分查找？

二分查找，就像它的名字一样直白，是一种在有序数组中查找特定元素的搜索算法。它的工作原理就像我们切蛋糕：每次都把问题的大小减半，直到找到那块“甜蜜的点”。

二分查找的步骤

1. 先有个有序数组：就像你的袜子都按大小排好一样。
2. 确定中间点：找到数组的中间位置，就像找到蛋糕的中心。
3. 比较中间值：看看中间位置的元素是不是你要找的。
4. 缩小搜索范围：如果中间值不是你要找的，根据大小，选择左半边或右半边继续查找。
5. 重复以上步骤：就像你不断切蛋糕，直到找到那块完美的甜点。