兔猫学院的“神秘插入点”挑战
🐰🐱 兔猫信奥学院：加菲老师的“神秘插入点”挑战
题目描述
在兔猫信奥学院的藏宝窖里，加菲老师将一排有序的魔法晶石按编号从小到大整齐排列。小兔和小猫需要将一颗新晶石（编号为 target）插入到正确的位置，以保持整个序列依然有序。若这颗晶石编号已经在序列中存在，则返回它原来的所在位置；否则返回它应该插入的位置（插入后数组下标从 0 开始）。
请你设计一个 时间复杂度为 O(log n) 的算法，帮助他们快速定位插入点或查找已有晶石的位置。
输入格式
n target
a0 a1 a2 … a(n−1)
- 第一行两个整数 n（晶石数量）和 target（新晶石编号）。
- 第二行包含 n 个整数 a0, a1, …, a(n−1)，表示已按升序排列且互不相同的晶石编号。
输出格式
- 输出一个整数，若 target 在数组中存在，输出它的下标（从 0 开始）；否则输出它应当插入的下标。
输入输出数据用例
样例 1
4 5
1 3 5 6
输出：
2
说明： 编号 5 已存在于位置 2。
样例 2
4 2
1 3 5 6
输出：
1
说明： 编号 2 不存在，插入后序列变 [1,2,3,5,6]，插入位置为 1。
样例 3
4 7
1 3 5 6
输出：
4
说明： 编号 7 大于所有元素，应插入末尾，下标为 4。