第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
如果没有找到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.联立两式,写方程,得结果
例题
t | 0 | 1 | 2 | ... | n |
---|---|---|---|---|---|
i | 1 | 2 | 4 | ... | 2^n |
找到关系:i = 2^t
找到关系:2^t = n ===> t=logn
2.双层循环
分析步骤:
1. 列出外层循环中i的变化值
2.列出内层语句的执行次数
3.求和写结果
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)
如果下标从0开始,第一次匹配失败,下次j肯定每次都要回到头开始,也就是下标为0处,而i应该回到下个位置开始,此时冲突的i和j一定是相等的,所以下标i=i-j+1即可。那对应如果是下标从1开始,那肯定就是j每次回到下标为1处喽,i = i -j +2处。
//设计在顺序存储结构上实现求子串算法(下标从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