二分法
二分法代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
int BinarySearch(vector<int> v, int value , int low, int high) {
if (v.size() <= 0) {
return -1;
}
while (low <= high) {
int mid = low + (high - low) / 2;
if (v[mid] == value) {
return mid;
}
else if (v[mid] > value) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return -1;
}
int BinarySearch2(vector<int> v, int value, int low, int high)
{
if (low > high)
return -1;
int mid = low + (high - low) / 2;
if (v[mid] == value)
return mid;
else if (v[mid] > value)
return BinarySearch2(v, value, low, mid - 1);
else
return BinarySearch2(v, value, mid + 1, high);
}
|
题目：
34. 在排序数组中查找元素的第一个和最后一个位置
69.x的平方根
153. 寻找旋转排序数组中的最小值
167. 两数之和 II - 输入有序数组
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
1
2
| 输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
|
示例 2:
1
2
| 输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
|
解法一
code-banner1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int i = 0, j = nums.size() - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] <= target) i = m + 1;
else j = m - 1;
}
int right = i;
if(j >= 0 && nums[j] != target) return {-1, -1};
if(j < 0) return {-1, -1};
i = 0; j = nums.size() - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] < target) i = m + 1;
else j = m - 1;
}
int left = j;
return {left + 1, right - 1};
}
};
|
解法二(还是二分法)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = 0, right = nums.size() -1,mid;
while (left <= right)
{
mid = (left + right) / 2;
if(nums[mid] > target)
right = mid - 1;
else if(nums[mid] < target)
left = mid + 1;
else if(nums[mid] == target)
{
if(nums[right] > target)
right--;
else if(nums[left] < target)
left++;
else if(nums[left] == target && nums[right] == target)
return {left , right};
}
}
return {-1,-1};
}
};
|
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
示例 2:
1
2
3
4
5
| 输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
|
代码（一看就会）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int mySqrt(int x) {
long l = 1;
long r = x;
if (x == 0) return 0;
if (x == 1) return 1;
while(l<r)
{
int mid = (l+r)/2;
if (x/mid == mid) {
return mid;
} else if (x/mid > mid) {
l = mid+1;
} else {
r = mid;
}
}
return l-1;
}
};
|
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
示例 1:
解题思路：
- 指针最终指向数组最大和最小的位置
- 左右两边不断靠近到整个数组最大值与最小值的分界点
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int findMin(vector<int>& nums) {
int left=0,right=nums.size()-1;
int min = nums[0];
if(nums[left] < nums[right]) return nums[left];
while(left < right)
{
int mid = (left + right) / 2;
if(right - left == 1)
return nums[left]>nums[right]?nums[right]:nums[left];
else if(nums[mid] > nums[right])
left = mid;
else if(nums[mid] < nums[right])
right = mid;
}
return min;
}
};
|
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例：
1
2
3
| 输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left=0,right = numbers.size() -1;
int sum = numbers[left] + numbers[right];
while ( sum != target)
{
sum = numbers[left] + numbers[right];
if( sum < target)
left++;
else if (sum > target){
right--;
}
else if ( sum == target){
return {left+1,right+1};
}
}
return {left+1,right+1};
}
};
|
