二分查找
1. 递归实现
int binarySearch(std::vector<int> &num, int start, int end, int target)
{
if (start > end) {
return -1;
}
int mid = start + (end - start) / 2;
if (target == num[mid]) {
return 1;
}
else if (target < num[mid]) {
return binarySearch(num, start, mid - 1, target);
}
else if (target > num[mid]) {
return binarySearch(num, mid + 1, mid, target);
}
}
2. 迭代实现
int binarySearch(std::vector<int> &num, int target)
{
int begin = 0;
int end = num.size() - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (num[mid] == target) {
return 1;
}
if (num[mid] > target) {
end = mid - 1;
}
if (num[mid] < target) {
begin = mid + 1;
}
}
return -1;
}
题目
1. 插入位置
题目
给定一个排序数组与目标值，该数组中没有重复元素，如果目标值在数组中出现，就返回目标在数组中的下标，如果目标在数组中没有出现，则返回目标应该插入的数组下标，使得目标插入之后，数组仍然有序。
思路
使用二分查找，如果存在就可以直接返回下标，如果不存在那么判断目标值与此时mid值的大小，确定位置。
代码
int searchInsertPosition(std::vector<int> &num, int target)
{
int index = -1; // 要返回的数组下标
int begin = 0;
int end = num.size() - 1;
int mid = 0;
while (index == -1) {
mid = (begin + end) / 2;
if (target == num[mid]) {
index = mid;
}
else if (target < num[mid]) {
if (mid == 0 || target > num[mid-1]) {
index = mid;
}
end = mid - 1;
}
else if (target > num[mid]) {
if (mid == num.size() - 1 || target < num[mid + 1]) {
index = mid + 1;
}
begin = mid + 1;
}
}
return index;
}
2. 区间查找
题目
图1. 题目
思路
- 先确定左边的端点，再确定右边的端点
- 怎么确定左右两边的端点？使用二分查找
代码实现
// 查找左端点
int leftBoundry(std::vector<int> &num, int target)
{
int begin = 0;
int end = num.size();
while (begin <= end) {
int mid = (begin + end) / 2;
if (target == num[mid]) {
if (mid == 0 || num[mid - 1] < target) {
return mid;
}
end = mid - 1;
}
else if (target < num[mid]) {
end = mid - 1;
}
else if (target > num[mid]) {
begin = mid + 1;
}
}
return -1;
}
// 查找右端点
int rightBoundry(std::vector<int> &num, int target)
{
int begin = 0;
int end = num.size();
while (begin <= end) {
int mid = (begin + end) / 2;
if (target == num[mid]) {
if (mid == num.size() - 1 || num[mid + 1] > target) {
return mid;
}
begin = mid + 1;
}
else if (target < num[mid]) {
end = mid - 1;
}
else if (target > num[mid]) {
begin = mid + 1;
}
}
return -1;
}
// 确定端点
void findBoundry(std::vector<int> &num, int target)
{
int left = leftBoundry(num, target);
int right = rightBoundry(num, target);
std:: cout << "left : " << left << std::endl;
std:: cout << "right: " << right << std::endl;
}
3. 旋转数组查找
题目
给定一个排序数组，数组中没有重复元素，且该数组可以在某个位置条件下旋转。给定目标target，求target是否在数组中出现，若出现返回元素所在数组下标，否则返回-1。
思路
- 考虑用二分查找，如果能够正确的找到说明没有问题，如果没有找到，是不能说明在数组中没有改数字的，因为数组进行了旋转之后，小的数可能在后面，这时候我们应该确定旋转区间，然后在旋转区间中继续查找，这时如果找不到，说明没有该数；
- 那么问题变成了怎么确定旋转区间的问题，充分利用旋转之后数组的性质来进行判断旋转区间
代码
class Solution {
public:
int search(std::vector<int> &num, int target)
{
int begin = 0;
int end = num.size();
int mid = 0;
while (begin <= end) {
mid = (begin + end) / 2;
if (num[mid] == target) { // 正常的二分查找，找到元素
return mid;
}
if (num[mid] > target) {
if (num[mid] > num[begin]) {
if (target >= num[begin]) {
end = mid - 1;
}
else {
begin = mid + 1;
}
}
else if (num[begin] > num[mid]) {
end = mid - 1;
}
}
if (num[mid] < target) {
if (num[begin] < num[mid]) {
begin = mid + 1;
}
else if (num[begin] > num[mid]) {
if (target >= num[begin]) {
end = mid - 1;
}
else {
begin = mid + 1;
}
}
else if (num[begin] == num[mid]) {
begin = mid + 1;
}
}
}
return -1;
}
};
