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

408 数据结构查找算法

时间:2024-07-28 20:18:40浏览次数:13  
标签: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对象......