数据结构-二分查找
数组理论基础
数组是存放在连续内存空间上的相同类型数据的集合。
举一个字符数组的例子，如图所示：
需要两点注意的是
- 数组下标都是从0开始的。
- 数组内存空间的地址是连续的
正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。
C++中二维数组在地址空间上是连续的。
二分查找
应用前提
数组为有序数组，同时还强调数组中无重复元素。
704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
c++实现
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2 ((right-left)>>1) + left
if (nums[middle] > target) {
right = middle - 1; // target 在左区间，所以[left, middle - 1]
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间，所以[middle + 1, right]
} else { // nums[middle] == target
return middle; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}
};
golang实现
func search(nums []int, target int) int {
left :=0
right := len(nums)-1
for left <= right {
middle := ((right-left)>>1)+left
if target < nums[middle] {
right = middle - 1
}else if target>nums[middle]{
left = middle+1
}else{
return middle
}
}
return -1
}
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
由于如果存在这个目标值，我们返回的索引也是pos，因此我们可以将两个条件合并得出最后的目标：「在一个有序数组中找第一个大于等于target 的下标」。
问题转化到这里，直接套用二分法即可，即不断用二分法逼近查找第一个大于等于target 的下标 。ans 初值设置为数组长度可以省略边界条件的判断，因为存在一种情况是 target 大于数组中的所有数，此时需要插入到数组长度的位置
c++实现
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int left=0,right = n-1;
int ans = n;
while(left<=right) {
int mid = ((right - left)>>1) + left;
if (target > nums[mid])
{
left=mid+1;
}else{
ans=mid;
right=mid-1;
}
}
return ans;
}
};
golang实现
func searchInsert(nums []int, target int) int {
var n int = len(nums)
var left int = 0
var right int = n-1
var ans = n
for left<=right {
mid := (right-left)>>1+left
if target <= nums[mid] {
ans=mid
right=mid-1
}else{
left=mid+1
}
}
return ans
}
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：你可以设计并实现时间复杂度为 O(\log n)的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
寻找target在数组里的左右边界，有如下三种情况：
-
情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
-
情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
-
情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
c++实现
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int leftBorder = getLeftBorder(nums, target);
int rightBorder = getRightBorder(nums, target);
// 情况一
if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
// 情况三
if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
// 情况二
return {-1, -1};
}
private:
int getRightBorder(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle - 1;
} else { // 寻找右边界，nums[middle] == target的时候更新left
left = middle + 1;
rightBorder = left;
}
}
return rightBorder;
}
int getLeftBorder(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
right = middle - 1;
leftBorder = right;
} else {
left = middle + 1;
}
}
return leftBorder;
}
};
go实现
func searchRange(nums []int, target int) []int {
leftBorder := getLeft(nums, target)
rightBorder := getRight(nums, target)
// 情况一
if leftBorder == -2 || rightBorder == -2 {
return []int{-1, -1}
}
// 情况三
if rightBorder - leftBorder > 1 {
return []int{leftBorder + 1, rightBorder - 1}
}
// 情况二
return []int{-1, -1}
}
func getLeft(nums []int, target int) int {
left, right := 0, len(nums)-1
border := -2 // 记录border没有被赋值的情况；这里不能赋值-1，target = num[0]时，会无法区分情况一和情况二
for left <= right { // []闭区间
mid := left + ((right - left) >> 1)
if nums[mid] >= target { // 找到第一个等于target的位置
right = mid - 1
border = right
} else {
left = mid + 1
}
}
return border
}
func getRight(nums []int, target int) int {
left, right := 0, len(nums) - 1
border := -2
for left <= right {
mid := left + ((right - left) >> 1)
if nums[mid] > target {
right = mid - 1
} else { // 找到第一个大于target的位置
left = mid + 1
border = left
}
}
return border
}
69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被舍去 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
实现思路：
由于x平方根的整数部分ans,满足 k^2 ≤x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。
二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案ans 后，也就不需要再去尝试 ans+1 了。
c++实现
class Solution {
public:
int mySqrt(int x) {
int l=0,r=x,ans=-1;
while(l<=r){
int mid = ((r-l)>>1) + l;
if ((long long)mid * mid <= x){
ans = mid;
l = mid + 1;
}else{
r = mid - 1;
}
}
return ans;
}
};
go实现
func mySqrt(x int) int {
l,r,ans := 0,x,-1
for l<=r {
mid := ((r-l)>>1)+l
if mid * mid <= x {
ans=mid
l = mid+1
}else{
r = mid-1
}
}
return ans
}
367. 有效的完全平方数
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
c++实现
class Solution {
public:
bool isPerfectSquare(int num) {
int l = 0,r = num;
while (l<=r){
int mid = ((r-l)>>1)+l;
long square = (long)mid*mid;
if (square == num)
return true;
else if (square > num)
r=mid-1;
else
l=mid+1;
}
return false;
}
};
go实现
func isPerfectSquare(num int) bool {
l,r := 0,num
for l<=r {
mid := ((r-l)>>1)+l
if mid * mid == num {
return true
}else if mid * mid > num {
r = mid-1
}else {
l = mid+1
}
}
return false
}
