NC105. 二分查找-II
描述
示例1
输入:
[1,2,4,4,5],4
输出:
2
说明:
从左到右，查找到第1个为4的，下标为2，返回2示例2
输入:
[1,2,4,4,5],3
输出:
-1
示例3
输入:
[1,1,1,1,1],1
输出:
0
C++ 解法, 执行用时: 6ms, 内存消耗: 2412KB, 提交时间: 2021-05-11
static const auto io_sync_off=[](){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 如果目标值存在返回下标，否则返回 -1
* @param nums int整型vector
* @param target int整型
* @return int整型
*/
int search(vector<int>& nums, int target) {
// write code here
if(nums.empty())
return -1;
int start = 0;
int end = nums.size() - 1;
int mid;
while(start < end)
{
if(nums[start] == nums[end] && nums[start] != target)
return -1;
if(end - start == 1)
{
if(nums[start] == target)
return start;
else if(nums[end] == target)
return end;
else
break;
}
//do
//{
mid = (start + end) >> 1;
if(nums[mid] < target)start = mid;
if(nums[mid] > target)end = mid;
if(nums[mid] == target)
{
for(int i=start;i<=mid;++i)
{
if(nums[i]==target){mid=i;break;}
}
return mid;
}
//}while(nums[mid] == target);
}
return -1;
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 2412KB, 提交时间: 2021-04-08
static const auto io_sync_off=[](){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 如果目标值存在返回下标，否则返回 -1
* @param nums int整型vector
* @param target int整型
* @return int整型
*/
int search(vector<int>& nums, int target) {
// write code here
int ans = 0;
if (nums.size() == 0)
return -1;
int left_index = 0;
int right_index = nums.size() - 1;
int middle_index = (left_index + right_index) / 2;
while (left_index < right_index)
{
if (nums.at(middle_index) == target) //找到了，往前看看有没有重复的
{
while (middle_index != 0 && nums.at(middle_index - 1) == nums.at(middle_index))
middle_index--;
return middle_index;
}
else if (nums.at(middle_index) < target) //如果中间值比目标值要小，往右查找
{
left_index = middle_index + 1;
middle_index = (left_index + right_index) / 2;
}
else //如果中间值比目标值要大，往左查找
{
right_index = middle_index - 1;
middle_index = (left_index + right_index) / 2;
}
}
if (left_index == right_index && nums.at(left_index) == target)
{
while (left_index != 0 && nums.at(left_index - 1) == nums.at(left_index))
left_index--;
return left_index;
}
else
return -1;
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 2416KB, 提交时间: 2021-05-12
static const auto io_sync_off=[](){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int search(vector<int>& nums, int target) {
// write code here
int left = 0;
int right = nums.size() - 1;
while(left < right){
int mid = left + (right - left)/2;
if(nums[mid] >= target)
right = mid;
else if(nums[mid] < target)
left = mid + 1;
}
return (right >= 0 && nums[right] == target)?right:-1;
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 2436KB, 提交时间: 2021-06-13
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 如果目标值存在返回下标，否则返回 -1
* @param nums int整型vector
* @param target int整型
* @return int整型
*/
int search(vector<int>& nums, int target) {
// write code here
if( nums.empty() ) return -1;
if(target <= nums[0]) return target == nums[0] ? 0 : -1;
if(target >= nums.back()){
if(target > nums.back()) return -1;
int idx = nums.size()-1;
while(nums[ --idx ] == nums.back()) ;
return idx+1;
}
int left(0), mid, right( nums.size()-1 );
while(left <= right)
{
mid = (left+right)>>1;
nums[mid] < target ? (left = mid+1) : (right = mid-1);
}
return nums[left] == target ? left : -1;
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 2452KB, 提交时间: 2021-08-10
static const auto io_sync_off=[](){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
// class Solution {
// public:
// /**
// * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
// *
// * 如果目标值存在返回下标，否则返回 -1
// * @param nums int整型vector
// * @param target int整型
// * @return int整型
// */
// int search(vector<int>& nums, int target) {
// // write code here
// if(nums.empty())
// return -1;
// int start = 0;
// int end = nums.size() - 1;
// int mid;
// while(start < end)
// {
// if(nums[start] == nums[end] && nums[start] != target)
// return -1;
// if(end - start == 1)
// {
// if(nums[start] == target)
// return start;
// else if(nums[end] == target)
// return end;
// else
// break;
// }
// mid = (start + end) >> 1;
// if(nums[mid] < target)start = mid;
// if(nums[mid] > target)end = mid;
// if(nums[mid] == target)
// {
// for(int i=start;i<=mid;++i)
// {
// if(nums[i]==target){mid=i;break;}
// }
// return mid;
// }
// //}while(nums[mid] == target);
// }
// return -1;
// }
// };
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.size()==0)
return -1;
int left=0;
int right=nums.size()-1;
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]<target)
left=mid+1;
else
right =mid;
}
return nums[left]==target?left:-1;
}
};