我们常常需要对数据进行查找,修改,查找数据有许多方法,我们先看看最简单的顺序查找
int main() { int i, k = 0; scanf("%d", &k); int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int sz = sizeof(arr) / sizeof(arr[0]); for (i = 0; i < sz; i++) { if (arr[i] == k) { printf("找到了,它是%d", arr[i]); } } return 0; }
1.如何判断查找完成,定义返回值含义,定义退出循环条件
2.如何处理边界问题,例如1 2 3 这个序列,当我们要查找1或者3时,会不会使程序出现BUG
3.对于数列来说,我们通常用整形存储其下标,二分查找若取下标中间数,则会出现什么样的问题?这些问题是否会影响我们的查找,若有问题,则应该如何规避?
通常情况,作为一个初学者,我甚至觉得二分查找过于简单,不值一提,最近经过思考,二分查找算法对于理论的要求并不是很高,但是若要把它变为有可行性的程序代码,则我们需要思考诸多的细节,否则这个代码写出来则是错误百出的。
如何解决第一个问题,因为我们了解的二分查找的思路其实就是折半查找,要有左边界与右边界我们才能确定中间元素,当左边界与右边界重合的时候,这时查找对象就变为一个元素的,若它也不是索要查找的对象,那么在所查找的集合中便没有所需的元素。这样我们就清楚地定义出来了所需参数,以及退出查找的条件。我们需要一个左边界以及右边界,还有中间元素,若右边界比左边界小(左比右大)时,退出循环,返回异常。若否,则执行 查找语句。
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include<Windows.h> int bin_search(int arr[], int left, int right, int key) { int mid = 0; while (left <= right) { mid = (left + right); if (arr[mid] > key) { right = mid - 1; } else if (arr[mid] < key) { left = mid + 1; } else return mid; } return -1; } int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; int left = 0; int right = sizeof(arr) / sizeof(arr[0]) - 1; int key = 7; int mid = 0; while (left <= right) { mid = (left + right) / 2; if (arr[mid] < key) left = mid + 1; else if (arr[mid] > key) right = mid - 1; else break; } if (right < left) printf("找不到\n"); else printf("找到了,下标为:%d", mid); }
二分查找:
在一个有序的序列中,找某个数据是否在该集合中,如果在打印该数据在集合中的下标,否则打印找不到 具体找的方式:
1. 找到数组的中间位置
2. 检测中间位置的数据是否与要查找的数据key相等
a: 相等,找到,打印下标,跳出循环
b: key < arr[mid], 则key可能在arr[mid]的左半侧,继续到左半侧进行二分查找
c: key > arr[mid], 则key可能在arr[mid]的右半侧,继续到右半侧进行二分查找
如果找到返回下标,否则继续,直到区间中没有元素时,说明key不在集合中,打印找不到 易错点:
1. right的右半侧区间取值,该值决定了后序的写法
2. while循环的条件是否有等号
3. 求中间位置的方法,直接相加除2容易造成溢出
4. 更改left和right的边界时,不确定是否要+1和-1
方法一,采用[left, right] 区间
#include <stdio.h> int main() { int arr[] = {1,2,3,4,5,6,7,8,9,10}; int key = 3; int left = 0; int right = sizeof(arr)/sizeof(arr[0])-1; // right位置的数据可以取到 while(left<=right) // right位置有数据,必须要添加=号 { int mid = left+(right-left)/2; if(arr[mid]>key) // key小于中间位置数据,说明key可能在左半侧,需要改变右边界 { right = mid-1; // right位置的数据可以取到,因此right=mid-1 } else if(arr[mid]<key)// key大于中间位置数据,说明key可能在右半侧,需要改变左边界 { left = mid+1; // left位置的数据可以取到,因此left=mid+1 } else { printf("找到了,下标是:%d\n", mid); break; } } if(left>right) printf("找不到\n"); return 0; }
方法二,采用[left, right) 区间
#include <stdio.h> int main() { int arr[] = {1,2,3,4,5,6,7,8,9,10}; int key = 3; int left = 0; int right = sizeof(arr)/sizeof(arr[0]); // right位置的数据取不到 while(left<right) // right位置没有数据,此处不需要添加= { int mid = left+(right-left)/2; if(arr[mid]>key) // key小于中间位置数据,说明key可能在左半侧,需要改变右边界 { right = mid; // right位置的数据取不到,因此right=mid,不需要减1 } else if(arr[mid]<key)// key大于中间位置数据,说明key可能在右半侧,需要改变左边界 { left = mid+1; // left位置的数据可以取到,因此left=mid+1 } else { printf("找到了,下标是:%d\n", mid); break; } } if(left>=right) printf("找不到\n"); return 0; }
二分查找的时间复杂度的问题:总共有n个元素,每次查找的区间大小就是n,n/2,n/4,…,n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数。由于n/2^k取整后>=1,即令n/2^k=1,可得k=log2n,(是以2为底,n的对数),所以时间复杂度可以表示O(logn),确实比顺序查找快不少,但是二分查找有一个较大的局限性:只能查找有序数组的元素,即组数字必须是升序或降序。
若有不足之处,希望批评指正