剑指 Offer II 068. 查找插入位置 #
- 标签:数组、二分查找
- 难度:简单
题目大意 #
给定一个排好序的数组 nums
,以及一个目标值 target
。
要求:在数组中找到目标值,并返回下标。如果找不到,则返回目标值按顺序插入数组的位置。
解题思路 #
二分查找法。利用两个指针 left
和 right
,分别指向数组首尾位置。每次用 left
和 right
中间位置上的元素值与目标值做比较,如果等于目标值,则返回当前位置。如果小于目标值,则更新 left
位置为 mid + 1
,继续查找。如果大于目标值,则更新 right
位置为 mid - 1
,继续查找。直到查找到目标值,或者 left > right
值时停止查找。然后返回 left
所在位置,即是代插入数组的位置。
代码 #
|
|