1.二分查找：（面对一个升序排列的数组）
class Soulution {
public:
int search(vector<int>& nums, int target) {//函数名（数组，变量）
int left = 0, right = nums.size() - 1;//声明变量left定义为数组的左边界，变量right定义为数组的右边界。
while(left <= right){
int mid = (right - left)/2 + left;//取数组的中间位置
int num = muns[mid];//取数组的中间位置的元素
if (num == target){//当寻找的变量等于数组中间位置的元素时，返回为中间未知的下标
return mid;
}else if (target < num){//当寻找的变量小于mid时，将右边界定义为mid-1，下次while循环计算mid的位置时，mid代表左边界的中间，从数组的左边开始寻找
right = mid -1
}else {//当寻找的变量大于mid时，将左边界定义为mid+1，下次while循环计算mid的位置时，mid代表右边界的中间，从数组的右边开始寻找
left = mid +1
}
}
return -1;//查找无果则返回-1
};
本算法耗时32ms，LeeCode上有更快的算法，最离谱的是有4ms的算法。
28ms：（可能是我才疏学浅，没看出这个和32ms的有什么区别）
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while(left <= right){
int mid = (right - left) / 2 + left;
int num = nums[mid];
if (num == target) {
return mid;
} else if (num > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
};
24ms：
下面是我对这个算法快于32ms算法的理解：
1.这个算法在第一个if和第二个if中先处理了基准情况，按照书上的说法，应该是这样理解的吧。
2.在第三个if中加入break提前终止。
class Solution {
public:
int search(vector<int>& nums, int target) {
int m, start = 0, end = nums.size()-1;//和第一个算法一样，先定义左边界和右边界
int flag = -1;
int tmp = 0;
while(start <= end){//当左边界小于右边界时
m = (start + end ) / 2;//m为数组的中间位置
tmp = nums[m];//tmp为数组中m位置上的数字
if(start == end){//当左边界等于右边界时，即数组中只有一个数字
if(target==nums[m]){//如果查找到变量target则返回m
return m;
}else{
return -1;//没有则返回-1
}
}
if (tmp == target){//当tmp==target时返回flag，且结束循环
flag = m;
break;
}else if (tmp > target){//接下来和32ms算法同理
end = m;
}
else {
start = m+1;
}
}
return flag;
}
};
20ms：
1.相比于32ms的算法，这个算法只声明了两个变量，第三个变量num用nums[num]代替，其他的原谅我才疏学浅，看不出来。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left<=right)
{
int mid=(right-left)/2+left;
if(nums[mid]==target)
{
return mid;
}
else if(nums[mid]>target)
{
right=mid-1;
}
else
{
left=mid+1;
}
}
return -1;
}
};
16ms：（好像和那个24ms的算法一样啊）
class Solution {
public:
int search(vector<int>& nums, int target) {
int m, start = 0, end = nums.size()-1;
int flag = -1;
int tmp = 0;
while(start <= end){
m = (start + end ) / 2;
tmp = nums[m];
if(start == end){
if(target==nums[m]){
return m;
}else{
return -1;
}
}
if (tmp == target){
flag = m;
break;
}else if (tmp > target){
end = m - 1;
}
else {
start = m + 1;
}
}
return flag;
}
};
12ms：
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();//初始化变量n为数组的长度
if(n == 0 ) return -1;//这里优先处理了基准情况，当数组长度为0时直接返回-1
int l = 0, r = n-1, mid ;//初始化变量为l，r为数组的左边界和右边界，声明变量mid为整型
while(l <= r){//和32ms算法一样
mid = (r+l)/2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid+1;
else if(nums[mid] > target) r = mid-1;
}
return -1;
}
};
8ms：
降维打击了。
int init = [] {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ofstream out("user.out");
for (string s; getline(cin, s); out << '\n') {
string t;
getline(cin, t);
int tar = stoi(t);
for (int i = 0, _i = 1, _n = s.length(); _i < _n; ++i, ++_i) {
bool _neg = false;
if (s[_i] == '-') ++_i, _neg = true;
int v = s[_i++] & 15;
while ((s[_i] & 15) < 10) v = v * 10 + (s[_i++] & 15);
if (_neg) v = -v;
if (v == tar) {
out << i;
goto next;
}
if (v > tar) break;
}
out << -1;
next:;
}
out.flush();
exit(0);
return 0;
}();
class Solution {
public:
int search(vector<int>, int) { return 0; }
};
4ms：
int init = [] {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ofstream out("user.out");
for (string s; getline(cin, s); out << '\n') {
string t;
getline(cin, t);
int tar = stoi(t);
for (int i = 0, _i = 1, _n = s.length(); _i < _n; ++i, ++_i) {
bool _neg = false;
if (s[_i] == '-') ++_i, _neg = true;
int v = s[_i++] & 15;
while ((s[_i] & 15) < 10) v = v * 10 + (s[_i++] & 15);
if (_neg) v = -v;
if (v == tar) {
out << i;
goto next;
}
if (v > tar) break;
}
out << -1;
next:;
}
out.flush();
exit(0);
return 0;
}();
class Solution {
public:
int search(vector<int>, int) { return 0; }
};
真是应了书上那句话，程序长的运行效率不一定低。
标签：二分,return,target,nums,int,LeeCode,left,例题,out From： https://www.cnblogs.com/apeiriaDolce/p/17207980.html