本文主要是介绍算法训练营——day1数组二分查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
数组是存放在连续空间上的相同数据类型的集合。
注意：下标从0开始；内存空间连续。
正因为数组的内存地址空间连续，所以在删除、添加元素的时候需要移动其他元素。
数组的元素不能删除，只能覆盖！
二维数组特殊
在C++中，二位数组在内存中也是连续的，相当于多个一维数组。
void test_arr() {int array[2][3] = {{0, 1, 2},{3, 4, 5}};cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}int main() {test_arr();
}Result：
0x7ffee4065820 0x7ffee4065824 0x7ffee4065828
0x7ffee406582c 0x7ffee4065830 0x7ffee4065834
由于是int类型，所有每个之间差4字节
而在Java中，由于是由JVM处理，所以毫无规则可言。
public static void test_arr() {int[][] arr = {{1, 2, 3}, {3, 4, 5}, {6, 7, 8}, {9,9,9}};System.out.println(arr[0]);System.out.println(arr[1]);System.out.println(arr[2]);System.out.println(arr[3]);
}
Result：
[I@7852e922
[I@4e25154f
[I@70dea4e
[I@5c647e05
练习题
1. 二分查找-力扣704（简单）
1.1 题目704. 二分查找
1.2 全闭区间写法
我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right]
因为定义target在[left, right]区间，所以有如下两点：
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
//Java代码：
class Solution {public int search(int[] nums, int target) {
// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算if(target<nums[0]||target>nums[nums.length-1]){return -1;}int left=0;int right=nums.length-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{return mid;}}return -1;}
}1.3 左闭右开
如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right)
有如下两点：
- while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
- if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]
//左闭右开
class Solution {public int search(int[] nums, int target) {int left=0;int right=nums.length;while(left<right){int mid = left+(right-left)/2;if(nums[mid]>target){right=mid;}else if(nums[mid]<target){left=mid+1;}else{return mid;}}return -1;}
}2 搜索位置-力扣35（简单）
2.1 题目35：搜索插入位置
2.2 二分解法（Java）
class Solution {public int searchInsert(int[] nums, int target) {//二分法int left = 0;int right = nums.length-1;while(left<=right){int mid = left+(right-left)/2;if(target==nums[mid]){return mid;}else if(target<nums[mid]){right=mid-1;}else if(target>nums[mid]){left=mid+1;}}return right+1;}
}2.3 C解法
class Solution {// lower_bound 返回最小的满足 nums[i] >= target 的 i// 如果数组为空，或者所有数都 < target，则返回 nums.size()// 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]// 闭区间写法int lower_bound(vector<int>& nums, int target) {int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right]while (left <= right) { // 区间不为空// 循环不变量：// nums[left-1] < target// nums[right+1] >= targetint mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1; // 范围缩小到 [mid+1, right]} else {right = mid - 1; // 范围缩小到 [left, mid-1]}}return left;}// 左闭右开区间写法int lower_bound2(vector<int>& nums, int target) {int left = 0, right = nums.size(); // 左闭右开区间 [left, right)while (left < right) { // 区间不为空// 循环不变量：// nums[left-1] < target// nums[right] >= targetint mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1; // 范围缩小到 [mid+1, right)} else {right = mid; // 范围缩小到 [left, mid)}}return left;}// 开区间写法int lower_bound3(vector<int>& nums, int target) {int left = -1, right = nums.size(); // 开区间 (left, right)while (left + 1 < right) { // 区间不为空// 循环不变量：// nums[left] < target// nums[right] >= targetint mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid; // 范围缩小到 (mid, right)} else {right = mid; // 范围缩小到 (left, mid)}}return right;}public:int searchInsert(vector<int>& nums, int target) {return lower_bound(nums, target); // 选择其中一种写法即可}
};3 查找元素第一位和最后一位的下标-力扣34（中等）
3.1 题目：34在排序数组中查找元素的第一个和最后一个位置
3.2 解法JAVA
寻找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}
//JAVA版本
class Solution {int[] searchRange(int[] nums, int target) {int leftBorder = getLeftBorder(nums, target);int rightBorder = getRightBorder(nums, target);// 情况一：不在数组范围内if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};// 情况三：找到了这个数字if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};// 情况二：在数组范围内但是没有这个数字return new int[]{-1, -1};}int getRightBorder(int[] nums, int target) {int left = 0;int right = nums.length - 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的时候更新leftleft = middle + 1;rightBorder = left;}}return rightBorder;}int getLeftBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新rightright = middle - 1;leftBorder = right;} else {left = middle + 1;}}return leftBorder;}
}3.2 解法C
//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的时候更新leftleft = 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的时候更新rightright = middle - 1;leftBorder = right;} else {left = middle + 1;}}return leftBorder;}
};4 平方根-力扣69（简单）
4.1 题目：x 的平方根
4.2 二分法求解
class Solution {public int mySqrt(int x) {int left=0;int ret=-1;int right=x;while(left<=right){int mid = left+(right-left)/2;if((long)mid*mid<=x){ret = mid;left=mid+1;}else{right=mid-1;}}return ret;}
}5 有效完全平方数-力扣367（简单）
5.1 题目：367. 有效的完全平方数
5.2 暴力与二分
//暴力解法
class Solution {public boolean isPerfectSquare(int num) {long x=1;long sq=1;while(sq<=num){if(sq==num){return true;}x++;sq=x*x;}return false;}
}class Solution {public boolean isPerfectSquare(int num) {//二分int left=0;int right=num;while(left<=right){int mid = left+(right-left)/2;long sq = (long) mid*mid;if(sq<num){left=mid+1;}else if(sq>num){right=mid-1;}else {return true;}}return false;}
}这篇关于算法训练营——day1数组二分查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
