链接: https://blog.nowcoder.net/n/d87ec4b614484f6ba1ae85beed081ff8?f=comment
题目:
请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
说明: 输出位置从1开始计算
思路: 二分查找,首先数组是由序的,先从中间的数开始找,如果不相等, 分两种情况:
-
中间的数小于 要查找的值
- 说明 要查找的值在后半部分,改变 查找范围继续从后半部分的中间找起.以此类推
-
中间的数大于 要查找的值
- 说明 要查找的值在前半部分,改变查找范围继续从前半部分的中间值找起,以此类推
代码:
- 边界判断: 题目是找一个 大于等于查找值 的位置,当查找值 小于给定数组的最后一个数,那么一定有解.( 审题很重要啊,我几度看成了要查找相等的值.....)
- 计算中间值的下标
3.循环查找 - 当 left == right 时,返回 当前的值
image.png
网友评论