算法之⼆分法查找（Python）⼆分法查找，也称为折半法，是⼀种在有序数组中查找特定元素的搜索算法。
⼆分法查找的思路如下：（1）⾸先，从数组的中间元素开始搜索，如果该元素正好是⽬标元素，则搜索过程结束，否则执⾏下⼀步。
（2）如果⽬标元素⼤于/⼩于中间元素，则在数组⼤于/⼩于中间元素的那⼀半区域查找，然后重复步骤的操作。
（3）如果某⼀步数组为空，则表⽰找不到⽬标元素。
以下是⼆分法常⽤的模板，包括查找指定数、查找左边界和右边界。
1. 查找指定数查找指定数是指只需要查找出指定数在数组中的索引即可，并不规定指定数在数组中所处的相对位置。
def binary_Search(nums, target):left, right = 0, len(nums)-1 # 搜索区间两边为闭while left <= right: # 注意停⽌条件，停⽌条件为[left, left+1]mid = (right + left) // 2# 找到指定数并返回其索引if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1 # 因为mid已经搜索过else:right = mid - 1return -1此处要注意的是：while循环的条件left <= right代表中⽌条件为[left, left+1]。
如果不加等号，则中⽌条件为[left,left]此时life并没有被搜索，是不正确的。
2. 左边界查找左边界查找是指需要查找出指定数在数组中第⼀次出现的位置的索引。
def left_Search(nums, target):left, right = 0, len(nums)-1 # 搜索区间两边为闭while left <= right:mid = (right + left) // 2if nums[mid] < target:left = mid + 1else:right = mid - 1if left >= len(nums) or nums[left] != target:return -1return left此处要注意的是：主要是要理解左边界查找和查找指定数的区别，在查找指定数时nums[mid] == target表⽰已经找到指定数，则返回该数索引即为结果。
二分法查找c语言程序二分法查找是一种在有序数组中查找某个特定值的技术，其核心思想是：首先选取数组中间位置的元素，如果该元素正好是要查找的元素，则查找过程结束；如果该元素大于要查找的元素，则在数组的前半部分再进行查找；如果该元素小于要查找的元素，则在数组的后半部分再进行查找。
重复以上过程，直到找到要查找的元素，或者查找范围为空。
用c语言实现二分法查找的程序：#include <stdio.h> // 声明函数 int binarySearch(int arr[], int left, int right, int key); // 主函数 int main() { // 定义数组int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // 计算数组的大小 int size = sizeof(arr) /sizeof(arr[0]); // 要查找的元素 int key = 4; // 用二分法查找 int result = binarySearch(arr, 0, size - 1, key); // 打印查找结果 if (result == -1) printf("元素不存在\n"); else printf("元素位置为：%d\n", result); return 0; } // 二分法查找函数 int binarySearch(int arr[], int left, intright, int key) { // 定义中间位置 intmid; // 当左侧位置小于右侧位置时，循环查找while (left <= right) { // 求出中间位置 mid = (left + right) / 2; //如果查找的key值等于中间位置的元素，则返回元素位置if (key == arr[mid]) return mid;// 如果查找的key值大于中间位置的元素，则从数组的右半部分开始查找 else if (key > arr[mid]) left = mid + 1; // 如果查找的key值小于中间位置的元素，则从数组的左半部分开始查找else right = mid - 1; } //如果查找不到，则返回-1 return -1; }。
算法图解（⼆分查找）⼆分查找假设你要查找电话本⾥k开头的⼈⾥可能会直接滑动到中间因为你知道k在中间位置因为电话本是abcdef排序的嘛定义：⼆分查找就指从中间开始查找的逻辑做法注：# ⼆分查找必须是有序序列返回其位置# ⽆序⽆法进⾏⼆分查找返回null例如：⼆分查找： 利⽤⼆分查找每次取中间数有⼩数可以向上或向下取整数 100以内的数字最多7次可以找出来普通查找： ⽽普通查找则是从头到位遍历最好的情况是1 ⼀次找出最差是100次⼆分查找随着元素的增加并不会改变太⼤普通查找则会随元素的增加⽽增加⽐如说⼀个字典内有240000个单词普通查找最差情况：240000次出结果⼆分查找最差情况：17次出结果这就很明显的突出了⼆分算法的优势####这⾥我⽤（）括号⾥的数字代表log的下标⽤⼆分查找最多需要log（2）n步其实就是利⽤对数运算：对数运算：定义：幂运算的逆运算例如：10**2 = 100 log（10）100 = 210**3 = 1000 log（10）1000=32**5 = 32 log（2）32 = 5如果有8个元素你最多需要查找3次因为long8 = 3（2**3=8）1024个元素最多需要检查10个元素因为 1024 = 10（2**10=1024）def binary(lst, item):low = 0high = len(lst) - 1while low <= high:mid = round((low + high) / 2)guess = lst[mid]if guess == item: # 猜对了return midif guess > item:high = mid - 1 # 猜⼤了else:low = mid + 1 # 猜⼩了return Nonemy_list = [1, 3, 5, 7, 9]print(binary(my_list, 3)) # 1 返回的元素下标索引是0开始的print(binary(my_list, -1)) # None 因为不存在-1元素运⾏时间： 线性时间（linear time） 100个数字最多猜100次 40亿猜40亿次最多猜的次数等于列表的长度 对数时间（或log时间） 100个数字最多猜7次 40亿猜32次⼤O表⽰法： 简单查找每个元素需要n次运⾏时间为O（n） ⼆分查找运⾏时间为O（log（n））⼤O表⽰法计算的是操作数 O（log n）对数时间包括⼆分查找 O（n）线性时间 O（n * log n）快速排序算法 O（n**2）速度较慢排序法算法 O（n！）⾮常慢的算法⼩结： ⼆分查找⽐简单查找快的多 O（log n）⽐O（n）快，需要搜索的元素越多，前者⽐后者就快的越多 算法运⾏时间并不以秒为单位 算法运⾏时间是从其增速的⾓度度量的 算法的运⾏时间⽤⼤O表⽰法表⽰。
C语⾔的算法--------⼆分法查找int find(int n,int a[],int l){int low=0;int high=l-1;int middle=0;while(low<high){middle=(low+high)>>1;if(n==a[middle]){printf("%d,%d",n,middle);return 1;}else if(n>a[middle])low=middle+1;elsehigh=middle-1;}return 0;}int main(){int a[]={2,3,5,6,7,8,9,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60};int l=sizeof(a)/sizeof(a[0]);int i=0,n;printf("arry content");for(i=0;i<l;i++){if(i%8==0)printf("\n");printf("%4d",a[i]);}printf("\nseach n is ");scanf("%d",&n);if(!find(n,a,l))printf("not fond");return 0;}⼆分查找的基本思想是：（设R[low..high]是当前的查找区间）（1）⾸先确定该区间的中点位置：（2）然后将待查的K值与R[mid].key⽐较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续⼆分查找，具体⽅法如下： ①若R[mid].key>K，则由表的有序性可知R[mid..n].keys均⼤于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的⼦表R[1..mid-1]中，故新的查找区间是左⼦表R[1..mid-1]。
