卡码网--数组篇(二分法)

系列文章目录

文章目录

系列文章目录
前言
数组
二分查找

前言

详情看：https://programmercarl.com/ 总结知识点用于复习

数组

概念: 数组是存放在连续内存空间上的相同类型数据的集合。

数组可以方便的通过下标索引的方式获取到下标对应的数据。

特点：

数组下标都是从0开始的。
数组内存空间的地址是连续的。
数组的元素是不能删的，只能覆盖。
二维数组在内存的空间地址是连续的。

正是因为数组在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

测试代码

#include <iostream>  
using namespace std;  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();
}

0x7ffc80278450 0x7ffc80278454 0x7ffc80278458
0x7ffc8027845c 0x7ffc80278460 0x7ffc80278464

打印出来，可以发现都相差4个字节。 60-5c=4 因为是十六进制 c是12 16-12=4
int类型四个字节。在C++中二维数组是连续分布的。

基础知识：
在C++中，数组是一种基本的数据结构，用于存储相同类型的数据元素。以下是数组的基础操作，包括定义、赋值和调用：

1. 定义数组
数组可以在声明时初始化，也可以先声明后赋值。
声明时初始化

int arr[5] = {1, 2, 3, 4, 5};
#先声明后赋值
int arr[5];  
arr[0] = 1;  
arr[1] = 2;  
arr[2] = 3;  
arr[3] = 4;  
arr[4] = 5;

2. 访问数组元素
使用索引来访问数组元素，索引从0开始。

int value = arr[0]; // 访问第一个元素

3. 修改数组元素
通过索引修改数组中的元素。

arr[0] = 10; // 修改第一个元素的值

4. 数组的大小
数组的大小在声明时就固定了，不能改变。可以使用sizeof运算符来获取数组的总大小（以字节为单位），或者使用sizeof(数组名) / sizeof(数组类型)来获取数组的元素个数。

int size = sizeof(arr) / sizeof(arr[0]); // 获取数组的元素个数

5. 遍历数组
使用循环结构遍历数组中的每个元素。

for (int i = 0; i < 5; i++) {  cout << arr[i] << " ";  
}

6. 数组作为函数参数
当数组作为函数参数时，实际上传递的是数组的指针。

void printArray(int arr[], int size) {  for (int i = 0; i < size; i++) {  cout << arr[i] << " ";  }  cout << endl;  
}

7. 多维数组
C++也支持多维数组，例如二维数组。

int matrix[3][3] = {  {1, 2, 3},  {4, 5, 6},  {7, 8, 9}  
};

访问二维数组的元素：

int value = matrix[0][1]; // 访问第一行第二列的元素

在C++中，字符串数组是一种用于存储多个字符串的数据结构。与基本数据类型数组类似，字符串数组也支持定义、赋值和调用等操作，但需要注意的是，字符串在C++中通常通过std::string类型来表示，或者在某些情况下使用字符数组（以空字符\0结尾）来表示。以下是关于字符串数组在C++中的基础操作：

定义字符串数组
使用std::string类型：
这是C++标准库中提供的字符串类型，使用它定义字符串数组非常直接。

#include <iostream>  
#include <string>  
using namespace std;  int main() {  string arr[5]; // 定义了一个可以存储5个std::string对象的数组  // ...  
}

也可以直接在定义时初始化：

string arr[5] = {"Apple", "Banana", "Cherry", "Date", "Elderberry"};

使用字符数组：
在C++中，你也可以使用字符数组（以\0结尾的字符序列）来模拟字符串数组。但这种方式更加底层，且操作起来相对复杂。

char str_array[3][20] = {"Hello", "world", "!"}; // 定义了一个二维字符数组，模拟字符串数组

赋值
使用std::string类型：可以直接使用赋值运算符=给std::string类型的数组元素赋值。

arr[0] = "New Apple"; // 将"New Apple"赋值给arr的第一个元素

使用字符数组：对于字符数组，你不能直接对整个数组进行赋值，但可以使用strcpy等函数来复制字符串。不过，在模拟字符串数组时（即二维字符数组），你通常是在初始化时就已经设定好了字符串内容。

调用
使用std::string类型：直接通过索引访问数组元素即可。

cout << arr[0] << endl; // 输出arr的第一个元素

使用字符数组：同样，通过索引访问二维数组的元素来引用字符串。

cout << str_array[0] << endl; // 输出第一个字符串"Hello"

注意，这里输出时不需要显式地指定字符串的结束位置，因为C++会根据\0自动判断字符串的结束。

4. 遍历
对于字符串数组（无论是std::string类型还是字符数组模拟的），你都可以使用循环结构来遍历数组中的每个字符串。

使用std::string类型：

for (int i = 0; i < 5; i++) {  cout << arr[i] << endl;  
}

使用字符数组：
遍历二维字符数组时，外层循环控制行（即不同的字符串），内层循环（如果需要的话）控制列（但在这种情况下，内层循环通常不需要，因为你是以整个行作为字符串来处理的）。

for (int i = 0; i < 3; i++) {  cout << str_array[i] << endl; // 直接输出整行，即一个字符串  
}

二分查找

力扣链接 704. 二分查找：https://leetcode.cn/problems/binary-search/description/

在这里插入图片描述
Step1: 读题可以提炼出 1. 数组是升序的 2. 无重复元素这两个条件是二分法的前提。
Step2: 二分法确定左右区间。

定义数组区间为[left,right]即左闭右闭。target属于[left,right]的话，left==right就是有意义的。则判断条件时while(left<=right）是有意义的。

if (nums[middle] > target) right 要赋值为 middle - 1。


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)/2if (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] == targetreturn middle; // 数组中找到目标值，直接返回下标}}// 未找到目标值return -1;}
};

一、基本概念
vector是C++标准模板库（STL）中的一个模板类，用于表示可以动态增长的数组。
它可以存储具有相同类型的数据项，这些数据项在内存中连续存储，因此可以通过下标快速访问。
二、特性
动态数组：vector在内部使用动态分配数组来存储元素，当元素数量超过当前容量时，vector会自动重新分配一个更大的数组，并将现有元素复制过去。
连续存储：与静态数组类似，vector中的元素在内存中也是连续存储的，这使得它可以通过指针算术来高效访问元素。
随机访问：由于vector中的元素是连续存储的，因此它支持随机访问迭代器，可以通过下标直接访问任意元素。
高效尾部操作：在vector的末尾添加或删除元素是非常高效的，因为这些操作不会导致内存重新分配（除非需要增加容量）。
内存管理：vector提供了reserve()和resize()成员函数来手动管理其容量和大小。reserve()用于增加容器的容量，而resize()用于改变容器的大小。
三、基本操作
定义与初始化：
可以使用默认构造函数来创建一个空的vector。std::vector vec; // 创建一个空的int类型vector
可以使用初始化列表来创建一个包含特定元素的vector。

std::vector<int> vec = {1, 2, 3, 4, 5}; // 创建一个包含5个整数的vector

可以使用另一个vector的范围来创建一个新的vector。

std::vector<int> originalVec = {1, 2, 3, 4, 5};  
std::vector<int> newVec(originalVec.begin(), originalVec.end()); // 使用originalVec的范围来创建newVec

元素访问：
可以使用下标运算符[]来访问vector中的元素。
可以使用at()成员函数来访问元素，该函数会进行范围检查。
插入与删除：
提供了push_back()成员函数来在vector的末尾添加一个元素。
提供了pop_back()成员函数来删除vector的最后一个元素。
提供了insert()和erase()成员函数来在vector的任意位置插入或删除元素。
遍历：
可以使用范围for循环来遍历vector中的元素。
可以使用迭代器来遍历vector，包括正向迭代器和反向迭代器。
容量与大小：
提供了size()成员函数来获取vector中元素的数量。
提供了capacity()成员函数来获取vector的容量。
提供了empty()成员函数来检查vector是否为空。

#include <iostream>  
#include <vector>  int main() {  // 创建一个空的vector  std::vector<int> vec;  // 向vector中添加元素  vec.push_back(1);  vec.push_back(2);  vec.push_back(3);  // 遍历vector并打印元素  for (int i = 0; i < vec.size(); ++i) {  std::cout << vec[i] << " ";  }  std::cout << std::endl;  // 使用范围for循环遍历vector并打印元素  for (auto& x : vec) {  std::cout << x << " ";  }  std::cout << std::endl;  // 删除vector的最后一个元素  vec.pop_back();  // 再次遍历vector并打印元素  for (auto& x : vec) {  std::cout << x << " ";  }  std::cout << std::endl;  return 0;  
}

Python 代码

class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1  # 定义target在左闭右闭的区间里，[left, right]while left <= right:middle = left + (right - left) // 2if nums[middle] > target:right = middle - 1  # target在左区间，所以[left, middle - 1]elif nums[middle] < target:left = middle + 1  # target在右区间，所以[middle + 1, right]else:return middle  # 数组中找到目标值，直接返回下标return -1