问题描述
有一个连续的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最小的下标。
编码
将上边的逻辑实现如下
int binary_search(int nums[], int begin, int end, int target)
{
//只要有一个越界就是没找到
if (begin < 0 || begin > end || end < 0)
{
return -1;
}
//找到中间值比较
int mid = (begin + end) / 2;
// cout << "mid is " << mid << endl;
//要找到的target在右半部分
if (target > nums[mid])
{
return binary_search(nums, mid + 1, end, target);
}
//要找到的target在左半部分
if (target < nums[mid])
{
return binary_search(nums, begin, mid - 1, target);
}
// cout << "nums[mid] is " << nums[mid] << endl;
//如果找到target相等的元素，需要向左移动找到最小索引
for (int i = mid; i > begin; i--)
{
if (target == nums[mid])
{
continue;
}
// cout << "i is " << endl;
return i + 1;
}
}
在main函数中调用如下
int nums[] = {0, 1, 1, 3, 3, 4};
int find = binary_search(nums, 0, sizeof(nums) / sizeof(int) - 1, 3);
cout << "find is " << find << endl;
int find2 = binary_search(nums, 0, sizeof(nums) / sizeof(int) - 1, 4);
cout << "find is " << find2 << endl;
int find3 = binary_search(nums, 0, sizeof(nums) / sizeof(int) - 1, 0);
cout << "find is " << find3 << endl;
程序输出如下
find is 3
find is 5
find is 0
总结
本文实现了用二分查找的方式找到给定的target值
源码链接https://gitee.com/secondtonone1/algorithms
更多算法实现点击下方链接
https://llfc.club/category?catid=22zkaaQaS2wMZRygv3qQVpRKpXI
