首页 > 编程语言 >408 数据结构查找算法

408 数据结构查找算法

时间：2024-07-28 20:18:40浏览次数：14  
标签：return int mid 查找 low key table 数据结构 408

第7章 查找

7.1二分查找

需求：在有序数组arr中，查找值为target的元素。若找到返回索引下标，否则返回-1

算法思路：找中间值，1.如果target＜中间值，在左半区间继续查找，即让high = mid - 1

​ 2.如果中间值＜target，在右半区间继续查找，即让low = mid + 1

​ 3.直到当low>high时证明没有找到值为target的元素，停止查找。

int binarysearch(int arr[], int target, int n) {
	int low = 0, high = n - 1;
	while (low <= high) {
		//int mid = low + ((high - low) >> 1);
		int mid = (low + high) / 2;
		if (target < arr[mid]) {
			high = mid - 1;
		}
		else if (arr[mid] < target) {
			low = mid + 1;
		}
		else {
			return mid;
		}
	}
	return -1;
}

int binarysearch2(int arr[], int target, int n) {
	int low = 0, high = n;
	while (low < high) {
		//int mid = low + ((high - low) >> 1);
		int mid = (low + high) / 2;
		if (target < arr[mid]) {
			high = mid;
		}
		else if (arr[mid] < target) {
			low = mid + 1;
		}
		else {
			return mid;
		}
	}
	return -1;
}

7.2刷题

1.在有序数组中，查找>=target最左侧的元素，若找到返回其下标，若未找到返回-1

int binaryFindMostLeft(int arr[], int target, int n) {
	int ans = -1;
	int low = 0, high = n - 1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (target <= arr[mid]) {
			ans = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	return ans;
}

2.在有序数组中，查找<=target最右侧的元素，若找到返回其下标，若未找到返回-1

int binaryFindLestRight(int arr[], int target, int n) {
	int ans = -1;
	int low = 0, high = n - 1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (target < arr[mid]) {	
			high = mid - 1;
		}
		else {
			ans = mid;
			low = mid + 1;
		}
	}
	return ans;
}

3.给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n)的算法解决此问题。

int binaryFindMostLeft1(int arr[], int target, int n) {
	int ans = -1;
	int low = 0, high = n - 1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (target == arr[mid]) {
			ans = mid;
			high = mid - 1;
		}
		else if(target < arr[mid]){
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	return ans;
}


int binaryFindLestRight1(int arr[], int target, int n) {
	int ans = -1;
	int low = 0, high = n - 1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (target == arr[mid]) {
			ans = mid;
			low = mid + 1;
		}
		else if (target < arr[mid]) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	return ans;

}



int* searchRange(int arr[], int target, int n) {
	int* res = (int*)malloc(sizeof(int) * 2);
	int start = binaryFindMostLeft1(arr, target, n);
	int end = binaryFindLestRight1(arr, target, n);
	res[0] = start;
	res[1] = end;
	return res;
}

4.给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

示例 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

image-20240320161225853

如果没有找到target的话，low即为插入点。

int searchInsert(int nums[], int n, int target) {
	int low = 0, high = n;
	while (low < high) {
		int mid = low + ((high - low) >> 1);

		if (target < nums[mid]) {
			high = mid;
		}
		else if (nums[mid] < target) {
			low = mid + 1;
		}
		else {
			return mid;
		}
	}
	return low;
}

5. 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

int mySqrt(int x) {
    if (x == 0) {
		return 0;
	}
	long long int ans = 0;
	for (long long int i = 1; i <= x; i++) {
		if (i * i >= x) {
			ans = i;
			break;
		}
	}
	return ans * ans ==x? ans: ans-1;
}

int mySqrt2(int x) {
	if (x == 0) {		//提前对0进行判断，为了防止后续再x/mid时出现除零异常。
		return 0;
	}
	int low = 1, high = x;
	while (low <= high) {
		int mid = low + ((high - low) >> 1);
		if (x / mid < mid) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	return low - 1;
}

6.给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。不能使用任何内置的库函数，如 sqrt 。

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

算法思路：利用二分法查找中间值元素，如果mid * mid > num,在左半区域查找，如果mid * mid <num ，在右半区域查找，否则相等返回true。

bool isPerfectSquare(int num) {
	long low = 1, high = num;
	while (low <= high) {
		long mid = low + ((high - low) >> 1);
		if (mid * mid > num) {
			high = mid - 1;
		}
		else if (mid * mid < num) {
			low = mid + 1;
		}
		else {
			return true;
		}
	}
	return false;
}

7.写出折半查找的递归算法。初始调用时，low为1，high为n

int fun(int arr[], int target, int L, int R) {
	if (L > R) {
		return -1; // 如果左边界大于右边界，说明未找到目标元素
	}

	int mid = L + (R - L) / 2; // 计算中间位置

	if (arr[mid-1] == target) {
		return mid-1; // 如果中间位置的元素等于目标元素，返回中间位置
	}
	else if (arr[mid-1] < target) {
		return fun(arr, target, mid + 1, R); // 如果中间位置的元素小于目标元素，递归在右半部分查找
	}
	else {
		return fun(arr, target, L, mid - 1); // 如果中间位置的元素大于目标元素，递归在左半部分查找
	}
}

int binarysearch2(int arr[], int target, int n) {
	return fun(arr, target, 1, n);
}

8.已知一个n阶矩阵A和一个目标值k。该矩阵无重复元素，每行从左到右升序排列，每
列从上到下升序排列。请设计一个在时间上尽可能高效的算法，判断矩阵中是否存在目标值k。

/*已知一个n阶矩阵A和一个目标值k。该矩阵无重复元素，每行从左到右升序排列，每
列从上到下升序排列。请设计一个在时间上尽可能高效的算法，判断矩阵中是否存在目标值k。
例如，矩阵为
				1   4   7 
				2   5   8
				3   6   9
目标值为8，判断存在。

*/
bool isExistTarget(int arr[n][n],int k, int n) {
	for (int i = 0; i < n; i++) {
		int low = 0, high = n - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (arr[i][mid] == k) {
				return true;
			}
			else if (k < arr[i][mid]) {
				high = mid - 1;
			}
			else {
				low = mid + 1;
			}
		}
	}
	return false;
}

bool isExistTarget(int arr[n][n], int k, int n) {
	int row = 0, col = n - 1;
	while (row < n && col >= 0) {
		if (arr[row][col] == k) {
			return true;
		}
		else if (arr[row][col] < k) {
			row++;
		}
		else {
			col--;
		}
	}
	return false;
}

7.3哈希表

#include<stdio.h>
#define TABLE_SIZE 8	//哈希表的最大长度
#define a 2				//a和b分别当做直接定值法中构造哈希函数的系数
#define b 1
#define p 7				//除留余数法中的不大于长度最近接长度的最大质数
typedef struct Student {
	char name[16];
	int age;
	float sorce;
}Student;
//哈希表结点结构
typedef struct HashNode {
	int key;
	Student *value;
	HashNode* next;	//用来拉链法的实现的，其他两种可以自行去掉
}HashNode;
//哈希表结构
typedef struct {
	HashNode* data[TABLE_SIZE];
//	HashNode table[TABLE_SIZE];
}HashTable;

7.3.1直接定值法构造函数+线性探测法解决冲突

int hash(int key) {
	return (a * key + b);
}

void initHashTable(HashTable& table) {
	for (int i = 0; i < TABLE_SIZE; i++) {
		table.data[i] = (HashNode*)malloc(sizeof(HashNode) * TABLE_SIZE);
		table.data[i]->key = -1;
		table.data[i]->value = NULL;
		//table.data[i]->next = NULL;
	}
}
void insert(HashTable &table, int key, Student *value) {
	int index = hash(key);
	table.data[index]->key = key;
	table.data[index]->value = value;
}

Student* search(HashTable table, int key) {
	int index = hash(key);
	if (index >= TABLE_SIZE) {
		return NULL;
	}else if (table.data[index] != NULL && table.data[index]->key == key) {
		return table.data[index]->value;
	}
	return NULL;
}


//打印哈希表
void printTable(HashTable table) {
	printf("%-12s | %-12s | %-12s\n", "Key", "Hash(key)", "Student");
	printf("--------------------------------------\n");
	for (int i = 0; i < TABLE_SIZE; i++) {
		Student* s = search(table, i);
		printf("%-12d | %-12d | ", i, hash(i));
		if (s) {
			printf("%-12s", s->name);
		}
		else {
			printf("%-12s", "Empty");
		}
		printf("\n");
	}
}

7.3.2除留余数法+线性探测法

int hash2(int key) {
	return key % p;
}

// 插入键值对到哈希表中
void insert2(HashTable& table, int key, Student* value) {
	int index = hash2(key);
	int pos = index;
	while (table.data[index]->key !=-1) {
		index = (index + 1) % p;  // 使用线性探测法解决冲突
		if (pos == index) {
			return;
		}
	}
	table.data[index]->key = key;
	table.data[index]->value = value;
}

Student* search2(HashTable table, int key) {
	int index = hash2(key);
	int pos = index;
	while (table.data[index]->key != key && table.data[index]->key != -1) {
		index = (index + 1) % p;  // 使用线性探测法查找
		if (pos == index) {
			return NULL;
		}
	}
	if (table.data[index]->key == key) {
		return table.data[index]->value;
	}
	else {
		return NULL;
	}
}

void printTable2(HashTable table) {
	for (int i = 0; i < TABLE_SIZE; i++) {
		printf("%d\t%d\t%s\n", i, table.data[i]->key, table.data[i]->value? table.data[i]->value->name:"Empty");
	}
}

7.3.3除留余数法+拉链法解决冲突

// 插入键值对到哈希表中
void insert3(HashTable& table, int key, Student* value) {
	int index = hash2(key);
	table.data[index]->key = key;
	//头插法创建
	HashNode* node =(HashNode*) malloc(sizeof(HashNode));
	node->key = key;
	node->value = value;
	node->next = table.data[index]->next;
	table.data[index]->next = node;
}

Student* search3(HashTable table, int key) {
	int index = hash(key);
	HashNode* cur = table.data[index]->next;
	while (cur) {
		if (cur->key == key) {
			return cur->value;
		}
		cur = cur->next;
	}
	return NULL;
}

// 打印哈希表
void printTable3(HashTable hashTable) {
	printf("Index\tKey\tData\n");
	for (int i = 0; i < TABLE_SIZE; i++) {
		printf("%d\t", i);
		HashNode* cur = hashTable.data[i]->next;
		while (cur != NULL) {
			printf("%d:%s -> ", cur->key, cur->value);
			cur = cur->next;
		}
		printf("NULL\n");
	}
}

补充

1.时间复杂度计算

1.单层循环

分析步骤：

1. 列出循环趟数t以及每轮循环i的变化值

2.找到t与i的关系

3.确定循环终止条件

4.联立两式，写方程，得结果

例题

image-20240310171208364

t 0 1 2 ... n
i 1 2 4 ... 2^n

找到关系：i = 2^t

找到关系：2^t = n  ===> t=logn

2.双层循环

分析步骤：

1. 列出外层循环中i的变化值

2.列出内层语句的执行次数

3.求和写结果

image-20240310172415015

i n-1 n-2 ... 3 2
内层执行次数 n-2 n-3 2 1

1+2+3...+n-2 = (n-2)(n-1)/2

2.字符串匹配

#define MAXSIZE 128
typedef struct {
	char ch[MAXSIZE];
	int length;
}String;

void createString(String& s, char str[], int n);
int indexOf(String s, String t);

int pattern(String s, String t,int next[]);
//创建字符串
void createString(String &s,char str[],int n) {
	for (int i = 0; i < n; i++) {
		s.ch[i] = str[i];
	}
	s.length = n;
}

2.1暴力匹配（实现思路1）

image-20240414230739105

如果下标从0开始，第一次匹配失败，下次j肯定每次都要回到头开始，也就是下标为0处，而i应该回到下个位置开始，此时冲突的i和j一定是相等的，所以下标i=i-j+1即可。那对应如果是下标从1开始，那肯定就是j每次回到下标为1处喽，i = i -j +2处。

image-20240414231026387

//设计在顺序存储结构上实现求子串算法（下标从0开始）
int indexOf(String s, String t) {
	int i = 0, j = 0, k = 0;
	while (i < s.length && j < t.length) {
		if (s.ch[i] == t.ch[j]) {
			i++;
			j++;
		}
		else {
			k++;
			i = k;
			//i = i - j + 1;
			j = 0;
		}
	}
	if (j == t.length) {
		return i - t.length;
	}
	else {
		return -1;
	}
}

2.1暴力匹配（实现思路2）



//设计在顺序存储结构上实现求子串算法（下标从1开始）
int indexOf2(String s, String t) {
	int i = 1, j = 1;
	while (i <= s.length && j <= t.length) {
		if (s.ch[i] == t.ch[j]) {
			i++;
			j++;
		}
		else {
			i = i - j + 2;
			j = 1;
		}
	}
	if (j > t.length) {
		return i - t.length;
	}
	else {
		return 0;
	}
}

2.2KMP算法（实现思路1）

//最原本的模式串匹配
int pattern(String s, String t, int next[]) {
	int i = 0, j = 0;
	while (i < s.length) {
		if (s.ch[i] == t.ch[j]) {
			i++;
			j++;
		}
		else if (j == 0) {
			i++;
		}
		else {
			j = next[j - 1];
		}
		if (j == t.length) {
			return i - j;
		}
	}
	return -1;
}

2.2KMP算法（实现思路2）

//补-1右移
int pattern2(String s, String t, int next[]) {
	int i = 0, j = 0;
	while (i < s.length) {
		if (s.ch[i] == t.ch[j]) {
			i++;
			j++;
		}
		else if (j == 0) {
			i++;
		}
		else {
			j = next[j];
		}
		if (j == t.length) {
			return i - j;
		}
	}
	return -1;
}

2.2KMP算法（实现思路3）

//下标从1开始
int pattern3(String s, String t, int next[]) {
	int i = 1, j = 1;
	while (i <= s.length) {
		if (j == 0 || s.ch[i] == t.ch[j]) {
			i++;
			j++;
		}
		/*else if (j == 0) {
			i++;
			j++;
		}*/
		else {
			j = next[j];
		}
		if (j > t.length) {
			return i - t.length;
		}
	}
	return 0;
}

2.2KMP算法（实现思路4）


//字符串下标从1开始,但是next从0开始
int pattern4(String s, String t, int next[]) {
	int i = 1, j = 1;
	while (i <= s.length) {
		if (j == 0 || s.ch[i] == t.ch[j]) {
			i++;
			j++;
		}
		/*else if (j == 0) {
			i++;
			j++;
		}*/
		else {
			j = next[j-1];
		}
		if (j > t.length) {
			return i - t.length;
		}
	}
	return 0;
}

测试代码

int main() {
	String s, t;
	String s1, t1;
	char str[] = "abcabcdabcdeabc\0";
	char str2[] = "abcde\0";
	int next[] = { 0,0,0,0,0 };
	int next2[] = { -1,0,0,0,0 };
	int next3[] = {999, 0,1,1,1,1 };
	int next4[] = { 0,1,1,1,1 };
	createString(s, str, 15);
	createString(t, str2, 5);
	int index = indexOf(s, t);
	printf("%d \n", index);
	int  res = pattern(s, t, next);
	printf("res = %d \n", res);
	int  res2 = pattern2(s, t, next2);
	printf("res2 = %d \n", res2);
	createString2(s1, str, 15);
	createString2(t1, str2, 5);
	//int next[] = { 0,1,2,3};
	int index2 = indexOf2(s1, t1);
	printf("%d \n", index2);
	int res3 = pattern3(s1, t1,next3);
	printf("%d \n", res3);
	int res4 = pattern4(s1, t1, next4);
	printf("%d \n", res4);
	return 0;
}

标签：return,int,mid,查找,low,key,table,数据结构,408
From： https://www.cnblogs.com/lingchuanfeng/p/18328815

相关文章

  • 408 数据结构栈算法
    第二章栈2.1顺序栈顺序栈的基本操作#defineMAXSIZE128typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; //用数组实现对栈中元素的存取 inttop; //栈顶指针 intlength; //栈的长度}SqStack;//初始化栈voidinitStack(SqStack&S);//判......
  • 408 数据结构队列算法
    第三章队列3.1顺序队列#defineMAXSIZE64typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; intfront; //队头指针 intrear; //队尾指针 intsize; //队列大小}SeQueue;//初始化队列voidinitQueue(SeQueue&Q){ //对数据元素进行初始化，防止出现......
  • 数组利用哨兵位查找元素
    数组利用哨兵位查找元素存储时把数组的下标0处空出，留着放哨兵位；从后向前遍历数组，直到找到目标元素，或者找到哨兵结束；根据被找到元素的所在位置判断元素是否在数组中存在在0处：不存在不在0处：存在实现：intsearchBySent(int*arr,inttarget){//把下标0赋值为......
  • CSP-S提高组数据结构算法模板大合集
    CSP-S算法总结2.2.1基础知识与编程环境无2.2.2C++程序设计2set/nultisetmap/multimapdeque/priority_queueSTL2.2.3数据结构P1886 滑动窗口/【模板】单调队列#include<iostream>usingnamespacestd;intn,k,a[1000005];intq[1000005],h,t;......
  • 数据结构-二叉树、堆、图
    一、线索二叉树规律：在有n个节点的链式二叉树中必定存在n+1个空指针链式二叉树中有很多的空指针，可以让这些空指针指向前一个节点\后一个节点，从而在有序遍历（中序遍历）二叉树时，不需要使用递归而通过循环即可以完成，并且效率要比递归快得多一定是搜索二叉树线索二叉树的结构typ......
  • C++ 数据结构体解析
    文章目录1.定义结构体2. 访问结构成员3. 结构作为函数参数4. 指向结构的指针5. typedef关键字1.定义结构体C/C++数组允许定义可存储相同类型数据项的变量，但是结构是C++中另一种用户自定义的可用的数据类型，它允许存储不同类型的数据项。结构用于表示一条记......
  • 从零开始学数据结构系列之第四章《克鲁斯卡尔算法应用场景-公交站问题》
    文章目录往期回顾某城市新增7个站点(A,B,C,D,E,F,G)，现在需要修路把7个站点连通各个站点的距离用边线表示(权)，比如A–B距离12公里问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?以上图为例，来对克鲁斯卡尔进行演示(假设用数组R保存......
  • 数据结构基础的学习
    数据结构：相互之间存在一种或多种特定关系的数据元素的集合。逻辑结构：集合：所有数据在同一个集合中，关系平等。线性：数据和数据之间是一对一的关系树：一对多图：多对多物理结构(在内存当中的存储关系)：顺序存储：数据存放在连续的存储单位中。逻辑关系和物理关系一致链式，数据存......
  • 数据结构的学习2
    树：n（n>=0）个结点的有限集合。n=0,空树。在任意一个非空树中，1，有且仅有一个特定的根结点2，当n>1时，其余结点可分为m个互不相交的有限集合T1,T2,T3.。。。。Tm，其中每一个集合又是一个树，并且称谓子树。结点拥有子树的个数称谓结点的度。度为0的结点称谓叶结点。度不为0，称谓......
  • 数据结构（Java）：反射&枚举&Lambda表达式
    目录1、反射1.1反射的定义1.2 反射机制的原理1.3反射相关类1.4 Class类1.4.1相关方法1.4.1.1 常用获得类相关的方法​编辑1.4.1.2 常用获得类中属性相关的方法 1.4.1.3 获得类中构造器相关的方法  1.4.1.4 获得类中方法相关的方法1.4.2获取Class对象......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99