by 光城

# 基于二分搜索法的floor与ceil

## 1.基本的二分搜索

```class Solution {
public:
int search1(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;

int left = 0, right = nums.size()-1;

// left与right均不会越界，可以取等
while (left <= right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;	// mid处理过了，需要mid+1
} else if (nums[mid] > target) {
right = mid-1;	// mid处理过了,需要mid-1
}
}
return -1;
}
};
```

```class Solution {
public:
int search2(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;

int left = 0, right = nums.size();

// right会越界
while (left < right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;	// mid处理过了，需要mid+1 left不会越界
} else if (nums[mid] > target) {
right = mid;	// 处理范围为[left,right)，right为开区间，不可取得right，一定要维护[left,right)这个条件不变
}
}
return -1;
}
};
```

```vector<int> nums={1,2,2,2,2,3,5};
int target=2;
```

## 2.最左侧index

```class Solution {
public:
int search3(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size()-1;

while (left <= right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
right=mid-1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid-1;
}
}

if(left==nums.size()) return -1;	// 如果最后left==nums.size()，表示nums中的所有元素都小于target,查找失败！
return nums[left] == target ? left : -1;
}
};
```

## 3.最右侧index

```class Solution {
public:
int search4(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size()-1;

while (left <= right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid-1;
}
}

if(right<0) return -1;	// 或者写if(left==0) return -1; 如果right<0，那么此时nums中所有元素均大于target
return nums[right] == target ? right : -1;
}
};
```

```int main() {
vector<int> nums={1,2,2,2,2,3,5};
int target=2;
cout<<Solution().search1(nums,target)<<endl;       // 3
cout<<Solution().search2(nums,target)<<endl;       // 3
// 寻找第一个等于target的index,最左侧index
cout<<Solution().search3(nums,target)<<endl;       // 1
cout<<Solution().search4(nums,target)<<endl;       // 4
return 0;
}
```

## 4.floor

```class Solution {
public:
int floor1(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size()-1;

while (left <= right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
right=mid-1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid-1;
}
}
// 所有元素均大于target
if (right < 0) return -1;
// 所有元素均小于target
if (left == nums.size()) return left - 1;
return nums[left] == target ? left : left-1;
}
};
```

```int floor2(vector<int>& nums, int target) {{

// 寻找比target小的最大索引
int left = -1, right = nums.size()-1;

// (left,right]
while( left < right ){
// 使用向上取整避免死循环
int mid = left + (right-left+1)/2;
if( nums[mid] >= target )
right = mid - 1;
else
left = mid;
}
// 如果该索引+1就是target本身, 该索引+1即为返回值
if( left + 1 < nums.size() && nums[left+1] == target )
return left + 1;
// 否则, 该索引即为返回值
return left;
}
```

## 5.ceil

```class Solution {
public:
int ceil1(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size()-1;

while (left <= right) {
int mid =left+ (right-left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid-1;
}
}

// 所有元素均大于target
if (right < 0) return 0;
// 所有元素均小于target
if (left == nums.size()) return left - 1;
return nums[right] == target ? right : right+1;
}
};

```

```int ceil2(vector<int>& nums, int target) {

// 寻找比target大的最小索引值
int left = 0, right = nums.size()-1;
while( left < right ){
// 使用普通的向下取整即可避免死循环
int mid = left + (right-left)/2;
if( nums[mid] <= target )
left = mid + 1;
else // arr[mid] > target
right = mid;
}
// 如果该索引-1就是target本身, 该索引+1即为返回值
if( right - 1 >= 0 && nums[right-1] == target )
return right-1;
// 否则, 该索引即为返回值
return right;
}

```

## 6.全部算法测试

```int main() {
vector<int> nums = {1, 2, 2, 2, 2, 3, 5};
int target = 2;
cout << Solution().search1(nums, target) << endl;       // 3
cout << Solution().search2(nums, target) << endl;       // 3
// 寻找第一个等于target的index,最左侧index
cout << Solution().search3(nums, target) << endl;       // 1
cout << Solution().search4(nums, target) << endl;       // 4
cout << Solution().ceil1(nums, 0) << endl;			// 0
cout << Solution().ceil2(nums, 0) << endl;			// 0
cout << Solution().ceil1(nums, 4) << endl;			// 5
cout << Solution().ceil2(nums, 4) << endl;			// 5
cout << Solution().ceil1(nums, 6) << endl;			// 6
cout << Solution().ceil2(nums, 6) << endl;			// 6

cout << Solution().floor1(nums, 0) << endl;			// -1
cout << Solution().floor2(nums, 0) << endl;			// -1
cout << Solution().floor1(nums, 4) << endl;			// 5
cout << Solution().floor2(nums, 4) << endl;			// 5
cout << Solution().floor1(nums, 6) << endl;			// 6
cout << Solution().floor2(nums, 6) << endl;			// 6
return 0;
}```

0 条评论

• ### 螺旋矩阵你听过？

昨天满课，我还是坚持来刷题了，写文时间是晚上10点45，刷题时间是10点，今日题目leetcode上的螺旋矩阵，这道题思路简单，实现困难，，对于考研的同学建议仔...

• ### 回归Android，继续刷题

这两天要做个安卓项目，哎，我之前是做安卓开发的，做了半年多，后面就没做了，距离现在至少1年半有余。

• ### 详解数组刷题上

一、初始定义及原地修改1.283. 移动零2.27. 移除元素3.26. 删除排序数组中的重复项4.80. 删除排序数组中的重复项 II二、基础思想应用1.75...

• ### [Leetcode][python]Find First and Last Position of Element in Sorted Array/在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

• ### 二分查找两种实现，附详细注释

链接：https://leetcode-cn.com/problems/binary-search

• ### Binary Search - 33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to y...

• ### 【剑指offer：在排序数组中查找数字】搜索左右边界：从两边向中间、二分查找

二分查找一般用来查找数字在有序数组中是否出现过。进一步想，它可以用来不断在子序列中搜索对应数字。所以，我们就可以用它来向左边子序列中不断搜索，确认左边界；同样的...

• ### OMG，我从来没想过，二分查找还有诗？！

二分查找是极其简单容易理解的一种算法，但它的变形与细节也是极其繁杂的，一不小心就容易踩坑。

• ### 二分查找算法细节详解

我相信对很多读者朋友来说，编写二分查找的算法代码属于玄学编程，虽然看起来很简单，就是会出错，要么会漏个等号，要么少加个 1。

• ### LeetCode<二分搜索> 33 & 81 Search in Rotated Sorted Array I&II

Suppose an array sorted in ascending order is rotated at some pivot unknown to y...