一、 二分查找
如无特殊说明，本文中所有用到的待查数组均为从小到大顺序。
1.1 无重复元素的二分查找
-
实现
C++
int binarySearch(int arr[], int n, int target)
{
int l = 0, r = n - 1;
while(l <= r)
{
int mid = l + (r-l)/2;
if(arr[mid] < target)
l = mid + 1;
else if(arr[mid] > target)
r = mid - 1;
else
return mid;
}
return -1;
}
python
def binary_search(arr, target):
l = 0; r = len(arr) - 1
while l <= r:
mid = (l + r) // 2;
if arr[mid] < target:
l = mid + 1
elif arr[mid] > target:
r = mid - 1
else
return mid
return -1
时间复杂度
二分查找每次将查找区间折半，故其时间复杂度为O(logN)。返回值
查找target失败时可有两种返回值：
-1 ：作为一个错误码表示未查找到target。
l ：l 可作为target在arr中的插入位置。
1.2 有重复元素的二分查找
在有重复元素的数组arr中，查找target的最右位置。
-
实现
C++
int duplicatedBS(int arr[], int target, int n)
{
int l = 0, r = n-1;
while(r-l > 1)
{
int mid = l + (r-l) / 2;
if(arr[mid] <= target)
l = mid;
else if(arr[mid] > target)
r = mid;
}
return l;
}
python
def duplicatedBS(arr, target):
l = 0; r = len(arr)-1
while r-l > 1:
mid = l + (r-l) // 2;
if arr[mid] <= target:
l = mid
else:
r = mid
return l
- 返回值
l: 当target存在时返回其最右位置；当target不存在时，返回小 于它的元素的最右位置；则l+1为其可插入位置。
- 终止条件
由于本例中l，r的更新取决于mid本身的值，故当r-l<=1时，l，r就不再更新；而当r-l==1时，已对数组中所有元素做出了判断，可退出循环。
二、相关问题
更新一些相关问题，包括但不限于leetcode中的问题。长期更新。
2.1 sqrt(x)
题目来自leetcode-69，计算并返回x的平方根，其中x保证为非负整数。由于返回类型是整数，因此将仅返回结果的整数部分。
- Solution
思路：设sqrtX为x的开方，则sqrtX = x / sqrtX。非负整数x的开方sqrtX必然在[0,x]之间，故考虑用二分查找法。
C++
int mySqrt(int x)
{
if (x == 0) //由于0不能做被除数，首先判断x是否为0
return 0;
int l = 1, r = x;
while (r - l > 1)
{
int mid = l + (r - l) / 2;
int sqrtX = x / mid;
if (mid == sqrtX)
return mid;
else if (mid > sqrtX)
r = mid;
else
l = mid;
}
return l;
}
python
注意与C++实现的循环终止条件不同，则返回值也不同
def mySqrt(self, x):
if x == 0:
return 0;
l = 1; r = x
while l <= r:
mid = l + (r - l) // 2
sqrt_x = x // mid
if mid == sqrt_x:
return mid;
if mid > sqrt_x:
r = mid - 1
else:
l = mid + 1
return r
