莱芜网站建设哪家好,两个 wordpress 合并,金华网站建设大型网页建设,怎么加入网站做微商城一、二分查询
1.概念
二分查询又被称为二分查找#xff0c;是一种在有序数组或序列中快速查找到对应元素的一种方法。每次查找范围缩小至原来的一半。
①前提条件
数组和列表必须有序#xff0c;否则无法进行二分查找。
②初始化
确定查找数组和列表的左边界#xff0…一、二分查询
1.概念
二分查询又被称为二分查找是一种在有序数组或序列中快速查找到对应元素的一种方法。每次查找范围缩小至原来的一半。
①前提条件
数组和列表必须有序否则无法进行二分查找。
②初始化
确定查找数组和列表的左边界通常为数组或列表第一个元素和右边界通常为数组和列表最后一个元素。
③循环
计算中间元素的序列比较中间元素和目标元素 如果中间元素等于目标元素那么查询结束返回中间元素的索引。如果目标元素大于中间元素说明目标元素在中间元素的右半部分那么左边界移到中间元素的右边。如果目标元素小于中间元素说明目标元素在中间元素的左半部分那么右边界移至中间元素的左边。
④结束条件
如果查找到目标元素的索引退出。
或者如果左边元素的索引大于右边元素说明目标元素不在数组内那么退出。
2.代码
int BinaryFindValue(const int* arr, int n, int value)
{int pos -1;if (n 1 || arr NULL) return pos;int left 0;int right n-1;while (leftright){int mid (right - left 1 ) / 2 left;if (value arr[mid]){right mid - 1;}else if (value arr[mid]){left mid 1;}else{pos mid;break;}} return pos;
}
int main()
{const int n 5;int arr[n] { 10,11,12,13,14 };int val 0;scanf(%d, val);int m BinaryFindValue(arr, n, val);printf(%d, m);
} 也可以将这一行写成这样
int mid (right - left 1 ) / 2 left;
修改后
int mid (right - left 1) 1 left; 是右移位操作符在计算机中执行二进制位的右移。 1 表示将二进制位向右移动一位相当于除以2。
注意这里有个问题
int mid ((right - left 1) 1) left;
加号大于右移操作符这样写的话是1left然后右移所以要给前面加上括号。
最终正确代码
int BinaryFindValue(const int* arr, int n, int value)
{int pos -1;if (n 1 || arr NULL) return pos;int left 0;int right n-1;while (leftright){int mid ((right - left 1) 1) left;if (value arr[mid]){right mid - 1;}else if (value arr[mid]){left mid 1;}else{pos mid;break;}} return pos;
}
int main()
{const int n 5;int arr[n] { 10,11,12,13,14 };int val 0;scanf(%d, val);int m BinaryFindValue(arr, n, val);printf(%d, m);
}
3. QA
Q:下面这个代码有问题请详细说明原因 A:
问题一是leftright判断条件,如果目标值是右边界值的话没有办法正确输出值。具体看下面的图示。 问题二是使用leftright/2如果left和right足够大他们的mid很可能超出最大整数的范围容易溢出。
修改
① 修改判断条件让leftright的时候退出循环这样就可以查找到边界的目标元素。
②修改查找中间元素的计算方式所以使用下面的方式只对区域进行取半。 4.优化一
如果我的序列中有多个重复的数字我想要找到最左端数字的下标你需要怎么做
添加一个判断
while (arr[mid - 1] value){mid--;}pos mid;break;
判断arr[mid]和value相等的时候它的前一个值是否也相等但是这样写是错误的因为如图在下面的示例中要找到12最左边元素的下标值mid-1判断到mid0下标的时候再-1会造成越界所以我们要对于判断条件增加。 增加一个条件mid-10防止越界行为老师在这里增加的条件是midleft也是相同的道理两种写法都可以。
//while ((midleft) (arr[mid - 1] value))
while ((mid-1 0) (arr[mid - 1] value)){mid--;}pos mid;break;
int BinaryFindValue(const int* arr, int n, int value)
{int pos -1;if (n 1 || arr NULL) return pos;int left 0;int right n-1;while (leftright){int mid ((right - left 1) 1) left;if (value arr[mid]){right mid - 1;}else if (value arr[mid]){left mid 1;}else{while ((mid-1 0) (arr[mid - 1] value)){mid--;}pos mid;break;}} return pos;
}
int main()
{const int n 13;int arr[n] { 12,12,12,13,13,13,13,13,24,24,24,25,26};int val 0;scanf(%d, val);int m BinaryFindValue(arr, n, val);printf(%d, m);
}
5.优化二
在这里查找最左端元素的时候你使用的是递归查询请问怎么样使用二分法继续进行最左端元素的查找。
使用递归方法继续查找呢
暂无思路待补充……
二、结构体
1.定义
结构体是由我们自己设计的一种类型。
结构体和数组的区别数组中所有元素的类型一致但是结构体中元素的类型不需要一致。
结构体的定义 struct Student //结构体名 { //成员列表 }; 这里结束的时候记得写分号哦
注意 在C语言中这里的Student是结构体名struct Student是结构体类型名。在进行创建结构体变量时需要使用结构体类型名创建。但是在C中结构体类型名和结构体名没有区别。 Student sx;//错误 struct Student sx;//正确 2.初始化
结构体的在声明的时候不需要初始化因为它此时还是类型不会开辟空间所以不能赋初值。在定义结构体变量时系统才会给结构体分配空间。
初始化顺序需要与结构体声明次序保持一致。
①使用花括号初始化
struct Student
{char s_name[20];int age;
};
int main()
{struct Student sx { lizeyu,23 };printf(%s %d\n, sx.s_name, sx.age);
}
结构体嵌套结构体初始化也是使用花括号初始化。
struct Date
{int year;int month;int day;
};
struct Student
{char s_name[20];Date birthday;int age;
};
int main()
{struct Student sx { lizeyu,{2000,8,21},23 };printf(%s %d\n, sx.s_name, sx.age);
}
或者写成这个样子也是可以的
struct Student sx { lizeyu,2000,8,21,23 };
3.结构体在内存中的存储
如果结构体内的数组是按照[ ]方式声明的定义变量的时候栈区为数组分配对应字节的空间。 如果声明结构体成员列表的时候使用指针的方式声明数组那么栈区的指针指向被存储在.data区的数组。
