我们常常需要对数据进行查找，修改，查找数据有许多方法，我们先看看最简单的顺序查找
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)，确实比顺序查找快不少，但是二分查找有一个较大的局限性:只能查找有序数组的元素，即组数字必须是升序或降序。
若有不足之处，希望批评指正
