问题描述
有一个连续的int数组,数组中的数据升序排序,数组中的数据不唯一,有重复数据,要求在数组中查找指定值为target的数据,返回target最小的下标,如果找到返回其最小的下标,如果没有找到,返回-1, 要求用 用二分查找的方式解决上述问题, 要求时间复杂度为Olog(n),空间复杂度为O(1)
举例 数组nums = [0,1,1,3,3,4], 查找target为1的数据最小的下标则返回1。如果查找target为100,则返回-1
解决思路
用二分查找解决上述问题,用一个数组中间的数据和target比较,如果中间值比target小,则说明target在中间值右侧。
如果中间值比target大,则说明target在中间值左侧。
如果中间值和target相等,则找到该target的位置,但是由于target不唯一,所以要向左移动,找到target最小的下标。
编码
将上边的逻辑实现如下
1 | int binary_search(int nums[], int begin, int end, int target) |
在main函数中调用如下
1 | int nums[] = {0, 1, 1, 3, 3, 4}; |
程序输出如下
1 | find is 3 |
总结
本文实现了用二分查找的方式找到给定的target值
源码链接https://gitee.com/secondtonone1/algorithms
更多算法实现点击下方链接
https://llfc.club/category?catid=22zkaaQaS2wMZRygv3qQVpRKpXI