二分查找法

二分法查找1、二分查找(Binary Search)二分查找又称折半查找，它是一种效率较高的查找方法。

二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。

不妨设有序表是递增有序的。

2、二分查找的基本思想二分查找的基本思想是：（设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]。

②类似地，若R[mid].key<K，则要查找的K必在mid的右子表R[mid+1..n]中，即新的查找区间是右子表R[mid+1..n]。

下一次查找是针对新的查找区间进行的。

因此，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。

这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。

3、二分查找算法int BinSearch(SeqList R，KeyType K){ //在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零int low=1，high=n，mid；//置当前查找区间上、下界的初值while(low<=high){ //当前查找区间R[low..high]非空mid=(low+high)/2；if(R[mid].key==K) return mid；//查找成功返回if(R[mid].kdy>K)high=mid-1; //继续在R[low..mid-1]中查找elselow=mid+1；//继续在R[mid+1..high]中查找}return 0；//当low>high时表示查找区间为空，查找失败} //BinSeareh二分查找算法亦很容易给出其递归程序【参见练习】4、二分查找算法的执行过程设算法的输入实例中有序的关键字序列为(05，13，19，21，37，56，64，75，80，88，92)要查找的关键字K分别是21和85。

c语言折中查找法折中查找法（也称为二分查找法）是一种在有序数组中查找特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且同样从中间元素开始比较。

如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

以下是一个用C语言实现的折中查找法：c复制代码#include<stdio.h>int binarySearch(int arr[], int l, int r, int x){if (r >= l) {int mid = l + (r - l) / 2;if (arr[mid] == x)return mid;if (arr[mid] > x)return binarySearch(arr, l, mid - 1, x); return binarySearch(arr, mid + 1, r, x); }return-1;}int main(void){int arr[] = {2, 3, 4, 10, 40};int n = sizeof(arr) / sizeof(arr[0]);int x = 10;int result = binarySearch(arr, 0, n - 1, x);(result == -1) ? printf("Element is not present in array"): printf("Element is present at index %d", result);return0;}这个程序首先定义了一个数组arr[]，然后使用binarySearch()函数查找特定的元素x。

如果x在数组中，函数将返回其索引；否则，返回-1。

⼆分查找与⼏种排序⽅法1. 递归⼆分查找2. 冒泡排序3. 选择排序4. 插⼊排序5. 归并排序6. 快速排序1、递归⼆分查找思想：使⽤⼆分查找的前提条件是数组元素必须已经排好序。

⼆分查找法⾸先将关键字与数组的中间元素进⾏⽐较，考虑下⾯三种情形：如果关键字⽐中间元素⼩，那么只需在前⼀半数组元素中进⾏递归查找；如果关键字与中间元素相等，则匹配成功，查找结束。

代码：public static int binarySearch(int[] list, int key){return binarySearch(list, key, 0, list.length - 1);}public static int binarySearch(int[] list, int key , int low, int high){//没有查找到if(low > high)return - low - 1;int mid = (low + high) / 2;if(key < list[mid]){return binarySearch(list, key, low, mid - 1);}else if(key == list[mid]){return mid;}else{return binarySearch(list, key, mid + 1, high);}}------------------------------------------------- 排序算法 ----------------------------------------------各排序算法的时间复杂度、空间复杂度、稳定性：（排序算法的稳定性：排序前后相等元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的）排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序 O(n^2) O(n^2) O(1)稳定选择排序 O(n^2) O(n^2) O(1)不稳定直接插⼊排序 O(n^2) O(n^2) O(1)稳定归并排序 O(nlogn) O(nlogn) O(n)稳定快速排序 O(nlogn) O(n^2) O(logn)不稳定堆排序 O(nlogn) O(nlogn) O(1)不稳定冒泡排序： 冒泡排序算法需要多次遍历数组（N-1次），在每次遍历中，⽐较连续相邻的元素。

二分查找是一种在有序数组中查找特定元素的搜索算法。

下面是一个用C++实现的二分查找程序：cpp复制代码#include<iostream>int binarySearch(int arr[], int left, int right, int x){while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == x)return mid;if (arr[mid] < x)left = mid + 1;elseright = mid - 1;}return-1; // 如果元素不在数组中，返回-1}int main(){int arr[] = {2, 3, 4, 10, 40};int n = sizeof(arr) / sizeof(arr[0]);int x = 10;int result = binarySearch(arr, 0, n - 1, x);(result == -1) ? std::cout << "Element is not present in array": std::cout << "Element is present at index " << result;return0;}在这个程序中，我们首先定义了一个名为binarySearch的函数，它接受一个数组、数组的左右索引以及要查找的元素。

然后，我们在while循环中使用二分查找法查找元素。

如果元素在数组中，我们返回它的索引；否则，我们返回-1表示元素不在数组中。

在main函数中，我们创建了一个数组并调用binarySearch 函数来查找特定的元素。

二分查找法实现及时间复杂度解析二分查找法，也称折半查找法，是一种高效的查找算法。

它的基本思想是将查找区间逐步缩小，直到找到目标元素或确认目标元素不存在。

在本文中，我们将介绍二分查找法的详细实现方法，并对其时间复杂度进行解析。

一、二分查找法的实现二分查找法适用于有序数组，它通过不断地将目标元素与数组中间的元素进行比较，以确定目标元素在数组中的位置。

下面是二分查找法的实现算法：1. 首先，确定查找的起始位置start和结束位置end。

一般情况下，start为数组的第一个元素的下标，end为数组的最后一个元素的下标。

2. 计算中间位置mid，mid的值等于(start + end) / 2。

3. 比较中间位置的元素与目标元素的大小关系。

如果中间位置的元素等于目标元素，则查找成功；如果中间位置的元素大于目标元素，则在左半部分继续查找；如果中间位置的元素小于目标元素，则在右半部分继续查找。

4. 如果找到目标元素，则返回目标元素所在的位置；如果数组中不存在目标元素，则返回-1表示查找失败。

5. 如果中间位置的元素与目标元素不相等，并且查找区间仍然存在，重复以上步骤。

6. 当start > end时，表示查找区间不存在，查找失败。

二、时间复杂度解析二分查找法的时间复杂度是O(logn)，其中n是数组的长度。

这是因为每次查找都将查找区间缩小一半，所以需要进行logn次查找。

在最坏的情况下，即要查找的目标元素位于数组的两头，需要进行logn次查找。

在平均情况下，二分查找法的时间复杂度依然是O(logn)。

需要注意的是，二分查找法只适用于有序数组。

如果数组是无序的，需要先进行排序，然后再进行二分查找。

三、总结二分查找法是一种高效的查找算法，适用于有序数组。

通过将查找区间逐步缩小，可以快速定位目标元素的位置。

同时，它的时间复杂度为O(logn)，在大规模数据查找时能够有效提高查找效率。

当然，二分查找法也有一些限制：首先，它要求数组是有序的；其次，数组的大小不能动态改变。

今日任务：今日我们来利用scratch进行一次二分查找算法的探究。

所谓二分查找法，就是这样一种查找思路，但是，它的使用有一定的局限性，被查找的数列必须是有序数列。

它的原理其Left=1 Right=51,3,5,7,11,33,37,42,56,79,88,102,113,117,128,142,155,161,177,208 Mid=311≠list（3）且11>list（3）,继续在前后半部分查找！Left=4 Right=51,3,5,7,11,33,37,42,56,79,88,102,113,117,128,142,155,161,177,208Mid=5 11=list（5），查找结束！返回列表位置5.如果是按照顺序查找法，需要查找5次，而用二分法只需要4次就可以查找到了，如果有序数列更复杂一些更长一些，二分法比顺序查找法的优势就更加明显！跟我来挑战Follow me：第一步：启动scratch软件；第二步：点击上方的“文件”→“保存”→保存到桌面，文件名：二分查找→点击“保存”；（第二步很很很重要，我希望所有的学生都能养成及时保存作品的好习惯！）第三步：首先我们先生成一个斐波那契数列程序较长，我们单独将二分法算法程序定义为一个单独地功能块（子程序），用的时候调用就可以了！还记得left 和right 、mid 分别是什么？再提醒一下！n=list(mid)最后直接调用这个功能块即可： 该程序的运行结果是：课后思考：（1） 试着总结一下二分法的优缺点？优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

（2）想一想，二分查找法的用途有哪些？二分查找法是最省优查找算法吗？有没有更高效的算法处理有序数列？（3）自己尝试设计出一个随即有序数列，尝试用二分法去查找结果。

二分查找法c语言二分查找法是一种常用的查找算法，也称为折半查找法。

它的主要思想是将查找区间不断地二分，直到找到目标元素或者确定目标元素不存在为止。

在本文中，我将详细介绍二分查找法的原理、应用场景以及具体实现。

一、原理二分查找法的原理非常简单。

首先，需要将待查找的区间确定为一个有序序列。

然后，通过将区间的中间位置的元素与目标元素进行比较，可以确定目标元素位于区间的哪一部分。

若中间元素等于目标元素，则查找成功；若中间元素大于目标元素，则目标元素位于区间的左半部分；若中间元素小于目标元素，则目标元素位于区间的右半部分。

然后，将区间缩小为目标元素所在的那一部分，重复上述步骤，直到找到目标元素或者确定目标元素不存在。

二、应用场景二分查找法适用于有序序列的查找。

在实际应用中，它常被用于在数组或有序列表中查找特定元素的位置或判断某一元素是否存在。

由于二分查找法的时间复杂度为O(logn)，远小于线性查找法的O(n)，因此它在大规模数据的查找中具有较高的效率。

三、具体实现下面是一个使用C语言实现的二分查找算法的示例代码：```c#include <stdio.h>int binarySearch(int arr[], int left, int right, int target) { while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}int main() {int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};int target = 12;int n = sizeof(arr) / sizeof(arr[0]);int result = binarySearch(arr, 0, n - 1, target);if (result == -1) {printf("目标元素不存在\n");} else {printf("目标元素在数组中的位置为：%d\n", result);}return 0;}```在上述代码中，binarySearch函数接受一个有序数组arr、查找区间的左边界left、查找区间的右边界right以及目标元素target作为参数。

二分法查找
二分查找也称折半查找（Binary Search），是一种在有序数组中查找目标值的算法。

它的基本思想是将数组分为两部分，然后判断目标值可能存在的那一部分，并继续在该部分中进行查找，以此逐渐缩小查找范围，直到找到目标值或确定不存在。

二分查找的基本实现步骤如下：
1. 确定数组的左边界和右边界，初始时左边界为0，右边界为数组长度减1。

2. 计算数组的中间位置mid，可以使用公式mid = (left + right) / 2。

3. 比较中间位置的元素与目标值的大小关系：
- 如果中间位置的元素等于目标值，则找到目标值，返回中间位置。

- 如果中间位置的元素大于目标值，则目标值可能在左侧部分，更新右边界为mid - 1。

- 如果中间位置的元素小于目标值，则目标值可能在右侧部分，更新左边界为mid + 1。

二分查找虽然思路简单，但在实现过程中需要注意细节，如循环中的不等号是否应该带等号，mid是否应该加一等。

分析这些细节的差异以及出现这些差异的原因，有助于更加灵活准确地实现二分查找算法。

顺序查找与二分查找对比近年来，随着信息技术的迅猛发展，各行各业对于数据的处理和检索需求越来越大。

其中，查找是一种常见并且重要的操作。

在众多查找算法中，顺序查找和二分查找是两种常见的方法。

本文将对这两种查找算法进行对比，并探讨它们在实际应用中的优劣势。

一、顺序查找顺序查找，又称线性查找，是一种简单直观的查找方式。

它的基本思想是逐个比对待查找元素和列表中的元素，直到找到匹配的元素或遍历完整个列表。

顺序查找的实现相对简单，只需要从列表的第一个元素开始逐个比对即可。

然而，顺序查找的缺点也是很明显的。

随着待查找元素数量的增加，顺序查找的时间复杂度由O(1)线性增长至O(n)，其中n为待查找元素的个数。

这意味着当数据量较大时，顺序查找的效率将大幅下降。

尤其是对于有序列表，顺序查找无法充分利用列表的有序性，在查找效率上存在明显的不足。

二、二分查找二分查找，又称折半查找，是一种高效的有序查找算法。

它利用了有序列表的特性，通过比较待查找元素与有序列表中间位置元素的大小关系，来确定待查找元素可能存在的区间，从而迅速缩小查找范围。

基于这个思想，二分查找可以将查找的时间复杂度从O(n)降低到O(log₂(n))，其中n为列表中元素的个数。

相比于顺序查找，二分查找的优势主要体现在高效性和适用范围上。

对于大规模有序列表，二分查找能够迅速定位目标元素，大大减少了查找的时间成本。

此外，在对近乎有序或近似有序列表进行查找时，二分查找仍能有较好的表现。

然而，二分查找也有其限制之处，它要求列表必须是有序的，这就增加了排序的前置操作，并且仅适用于静态列表，即在查找过程中列表不发生变化。

三、实际应用中的对比在实际应用中，选择合适的查找算法需要考虑到数据规模、数据的有序性以及查找的频率等因素。

下面针对不同场景进行对比：1. 对于小规模或基本有序的数据集合，顺序查找往往是一个简单而直接的选择。

顺序查找代码简单，易于实现，并且不要求待查找元素有序，适用于轻量级的查找操作。

分治算法——二分查找法分治算法是一种将问题划分成多个独立的子问题来解决的算法思想，通常用于解决一些具有重复性的问题。

其中，二分查找法是分治算法的典型应用之一，被广泛应用于各种排序和查找问题中。

二分查找法，顾名思义，就是将要查找的元素不断与中间元素进行比较，然后根据比较结果来确定继续在哪个半区间进行查找，直到找到目标元素或者确定目标元素不存在为止。

二分查找法的前提是待查找的数组或列表必须是有序的。

具体的实现方法是，首先确定查找范围的起始位置和结束位置，然后求取中间位置的下标。

接下来，将待查找的元素与中间位置的元素进行比较，若相等，则直接返回中间位置；若待查找元素小于中间位置的元素，则继续在左半区间进行查找，即将查找范围的结束位置调整为中间位置的前一个位置；若待查找元素大于中间位置的元素，则继续在右半区间进行查找，即将查找范围的起始位置调整为中间位置的后一个位置。

然后重复上述过程，直到查找到目标元素或者确定目标元素不存在。

二分查找法的时间复杂度为O(logN)，其中N表示待查找的元素个数。

这是因为在每一次比较过程中，查找范围都会减半。

在最坏的情况下，即待查找的元素不在数组或列表中时，需要进行logN次比较才能确定。

二分查找法的应用非常广泛，特别是在查找和排序领域。

它可以用于在有序数组或列表中查找一些元素的位置，也可以用于确定一些元素是否存在于有序数组或列表中。

另外，二分查找法还可以用于解决其他一些问题，例如旋转排序数组、插入位置等。

尽管二分查找法的实现方法相对简单，但在具体应用时还需要注意一些细节问题。

首先，待查找的数组或列表必须是有序的，如果无序，则需要先进行排序。

其次，要注意查找范围的起始位置和结束位置的变化，以免出现越界访问的错误。

另外，如果数组或列表中存在相同的元素，需根据具体情况来确定返回的位置。

综上所述，二分查找法是一种高效的算法，适用于有序数组或列表的查找问题。

它的时间复杂度为O(logN)，在实际应用中极大地提高了效率。

二分查找二分查找算法基本思想二分查找算法的前置条件是,一个已经排序好的序列(在本篇文章中为了说明问题的方便,假设这个序列是升序排列的),这样在查找所要查找的元素时,首先与序列中间的元素进行比较,如果大于这个元素,就在当前序列的后半部分继续查找,如果小于这个元素,就在当前序列的前半部分继续查找,直到找到相同的元素,或者所查找的序列范围为空为止.用伪代码来表示, 二分查找算法大致是这个样子的:left = 0, right = n -1while (left <= right)mid = (left + right) / 2casex[mid] < t: left = mid + 1;x[mid] = t: p = mid; break;x[mid] > t: right = mid -1;return -1;第一个正确的程序根据前面给出的算法思想和伪代码, 我们给出第一个正确的程序,但是,它还有一些小的问题,后面会讲到int search(int array[], int n, int v){int left, right, middle;left = 0, right = n - 1;while (left <= right){middle = (left + right) / 2;if (array[middle] > v){right = middle;}else if (array[middle] < v){left = middle;}else{return middle;}}return -1;}下面,讲讲在编写二分查找算法时可能出现的一些问题.边界错误造成的问题二分查找算法的边界,一般来说分两种情况,一种是左闭右开区间,类似于[left, right),一种是左闭右闭区间,类似于[left, right].需要注意的是, 循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则,也就是说,如果循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此.如果两者不一致,会造成程序的错误.比如下面就是错误的二分查找算法:int search_bad(int array[], int n, int v){int left, right, middle;left = 0, right = n;while (left < right){middle = (left + right) / 2;if (array[middle] > v){right = middle - 1;}else if (array[middle] < v){left = middle + 1;}else{return middle;}}return -1;}这个算法的错误在于, 在循环初始化的时候,初始化right=n,也就是采用的是左闭右开区间,而当满足array[middle] > v的条件是, v如果存在的话应该在[left, middle)区间中,但是这里却把right赋值为middle - 1了,这样,如果恰巧middle-1就是查找的元素,那么就会找不到这个元素.下面给出两个算法, 分别是正确的左闭右闭和左闭右开区间算法,可以与上面的进行比较: （下面这两个算法是正确的）int search2(int array[], int n, int v){int left, right, middle;left = 0, right = n - 1;while (left <= right){middle = (left + right) / 2;if (array[middle] > v){right = middle - 1;}else if (array[middle] < v){left = middle + 1;}else{return middle;}}return -1;}int search3(int array[], int n, int v){int left, right, middle;left = 0, right = n;while (left < right){middle = (left + right) / 2;if (array[middle] > v){right = middle;}else if (array[middle] < v){left = middle + 1;}else{return middle;}}return -1;}死循环上面的情况还只是把边界的其中一个写错, 也就是右边的边界值写错, 如果两者同时都写错的话,可能会造成死循环,比如下面的这个程序:int search_bad2(int array[], int n, int v){int left, right, middle;left = 0, right = n - 1;while (left <= right){middle = (left + right) / 2;if (array[middle] > v){right = middle;}else if (array[middle] < v){left = middle;}else{return middle;}}return -1;}这个程序采用的是左闭右闭的区间.但是,当array[middle] > v的时候,那么下一次查找的区间应该为[middle + 1, right], 而这里变成了[middle, right];当array[middle] < v的时候,那么下一次查找的区间应该为[left, middle - 1], 而这里变成了[left, middle].两个边界的选择都出现了问题, 因此,有可能出现某次查找时始终在这两个范围中轮换,造成了程序的死循环.溢出前面解决了边界选择时可能出现的问题, 下面来解决另一个问题,其实这个问题严格的说不属于算法问题,不过我注意到很多地方都没有提到,我觉得还是提一下比较好.在循环体内,计算中间位置的时候,使用的是这个表达式:middle = (left + right) / 2;假如,left与right之和超过了所在类型的表示范围的话,那么middle就不会得到正确的值. 所以,更稳妥的做法应该是这样的:middle = left + (right - left) / 2;更完善的算法前面我们说了,给出的第一个算法是一个"正确"的程序, 但是还有一些小的问题.首先, 如果序列中有多个相同的元素时,查找的时候不见得每次都会返回第一个元素的位置, 比如考虑一种极端情况:序列中都只有一个相同的元素,那么去查找这个元素时,显然返回的是中间元素的位置.其次, 前面给出的算法中,每次循环体中都有三次情况,两次比较,有没有办法减少比较的数量进一步的优化程序?<<编程珠玑>>中给出了解决这两个问题的算法,结合前面提到溢出问题我对middle的计算也做了修改:int search4(int array[], int n, int v){int left, right, middle;left = -1, right = n;while (left + 1 != right)//这个循环维持的条件是left<right && array[left]<v<=array[right],所以到最后的时候，{//如果可以找到目标，则只剩下两个数，并且满足 array[left]<v<=array[right],是要查找的数是rightmiddle = left + （right －left) / 2;if (array[middle] < v)//必须保证array[left]<v<=array[right]，所以left = middle;{//如果left =middle+1,则有可能出现array[left]<=v的情况left = middle;}else{right = middle;}}if (right >= n || array[right] != v){right = -1;}return right;}这个算法是所有这里给出的算法中最完善的一个,正确,精确且效率高.但是这个算法的还是不能很好的理解可以用下面的算法，可以找出满足条件的数[cpp]view plaincopy1.int Bi_Search(int a[],int n,int b)//2.{//返回等于b的第一个3.if(n==0)4.return -1;5.int low = 0;6.int high = n-1;7.int last = -1;//用last记录上一次满足条件的下标8.while (low<=high)9. {10.int mid = low +(high-low)/2;11.if (a[mid]==b)12. {13. last = mid;14. high = mid -1;15. }16.else if(a[mid]>b)17. high = mid -1;18.else19. low = mid +1;20. }21.22.return last;23.24.}25.int Bi_Search1(int a[],int n,int b)//大于b的第一个数26.{27.if(n<=0)28.return -1;29.int last = -1;30.int low = 0;31.int high = n-1;32.while (low<=high)33. {34.int mid = low +(high - low)/2;35.if(a[mid]>b)36. {37. last = mid;38. high = mid -1;39. }40.else if (a[mid]<=b)41. {42. low =mid +1;43. }44. }45.46.return last;47.}查找（二）：二分查找一、二分查找(Binary Search)二分查找又称折半查找，它是一种效率较高的查找方法。

python二分查找法编程二分查找算法（Binary Search Algorithm）是一种在有序数组中查找特定元素的搜索算法。

该算法通过反复将数组一分为二，并与目标值进行比较，从而快速缩小查找范围，直到找到目标值或确定目标值不存在。

下面是一个使用 Python 实现二分查找算法的示例代码：```pythondef binary_search(arr, target):low = 0high = len(arr) - 1mid = 0while low <= high:mid = (high + low) // 2# 如果中间元素等于目标值，返回中间元素的索引if arr[mid] == target:return mid# 如果中间元素大于目标值，将 high 调整到 mid - 1elif arr[mid] > target:high = mid - 1# 如果中间元素小于目标值，将 low 调整到 mid + 1else:low = mid + 1# 如果循环结束还没有找到目标值，返回-1return -1# 测试代码arr = [1, 3, 5, 7, 9, 11, 13]target = 7result = binary_search(arr, target)if result!= -1:print(f"目标元素 {target} 在数组中的索引为 {result}")else:print(f"目标元素 {target} 不在数组中")```上述代码中，`binary_search`函数接受一个有序数组`arr`和目标值`target`作为参数。

通过反复将数组一分为二，并与目标值进行比较，不断缩小查找范围，直到找到目标值或确定目标值不存在。

如果找到目标值，则返回其索引；否则返回-1。

希望这个示例对你有帮助。

如果你有任何其他问题，请随时提问。

C语⾔⼁⼆分查找算法详解（含⽰例代码）⼆分査找也称折半査找，其优点是查找速度快，缺点是要求所要査找的数据必须是有序序列。

该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进⾏⽐较，如果相等，则表⽰査找成功，否则将以该位置为基准将所要査找的序列分为左右两部分。

接下来根据所要査找序列的升降序规律及中间元素与所查找元素的⼤⼩关系，来选择所要査找元素可能存在的那部分序列，对其采⽤同样的⽅法进⾏査找，直⾄能够确定所要查找的元素是否存在，具体的使⽤⽅法可通过下⾯的代码具体了解。

#include <stdio.h>binarySearch(inta[], intn, intkey){intlow = 0;inthigh = n - 1;while(low<= high){intmid = (low + high)/2;intmidVal = a[mid];if(midVal<key)low = mid + 1;elseif(midVal>key)high = mid - 1;elsereturnmid;}return-1;}intmain(){inti, val, ret;inta[8]={-32, 12, 16, 24, 36, 45, 59, 98};for(i=0; i<8; i++)printf("%d\t", a[i]);printf("\n请输⼈所要查找的元素：");scanf("%d",&val);ret = binarySearch(a,8,val);if(-1 == ret)printf("查找失败 \n");elseprintf("查找成功 \n");return0;}运⾏结果：-32 12 16 24 36 45 59 98请输⼊所要查找的元素：12查找成功在上⾯的代码中，我们成功地通过⼆分査找算法实现了查找功能，其实现过程如下图所⽰。

数据结构50：⼆分查找法（折半查找法）折半查找，也称⼆分查找，在某些情况下相⽐于顺序查找，使⽤折半查找算法的效率更⾼。

但是该算法的使⽤的前提是静态查找表中的数据必须是有序的。

例如，在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使⽤折半查找算法查找数据之前，需要⾸先对该表中的数据按照所查的关键字进⾏排序：{5,13,19,21,37,56,64,75,80,88,92}。

在折半查找之前对查找表按照所查的关键字进⾏排序的意思是：若查找表中存储的数据元素含有多个关键字时，使⽤哪种关键字做折半查找，就需要提前以该关键字对所有数据进⾏排序。

折半查找算法对静态查找表{5,13,19,21,37,56,64,75,80,88,92}采⽤折半查找算法查找关键字为 21 的过程为：图 1 折半查找的过程（a）如上图 1 所⽰，指针 low 和 high 分别指向查找表的第⼀个关键字和最后⼀个关键字，指针 mid 指向处于 low 和 high 指针中间位置的关键字。

在查找的过程中每次都同 mid 指向的关键字进⾏⽐较，由于整个表中的数据是有序的，因此在⽐较之后就可以知道要查找的关键字的⼤致位置。

例如在查找关键字 21 时，⾸先同 56 作⽐较，由于21 < 56，⽽且这个查找表是按照升序进⾏排序的，所以可以判定如果静态查找表中有 21这个关键字，就⼀定存在于 low 和 mid 指向的区域中间。

因此，再次遍历时需要更新 high 指针和 mid 指针的位置，令 high 指针移动到 mid 指针的左侧⼀个位置上，同时令 mid 重新指向 low 指针和 high 指针的中间位置。

如图 2 所⽰：图 2 折半查找的过程（b）同样，⽤ 21 同 mid 指针指向的 19 作⽐较，19 < 21，所以可以判定 21 如果存在，肯定处于 mid 和 high 指向的区域中。

所以令 low 指向 mid 右侧⼀个位置上，同时更新 mid 的位置。

二分查找法.按照从小到大的顺序,输入n个整数并存入数组a中,然后在数组a中查找给定按照从小到大的顺序，输入n个整数并存入数组a中，然后在数组a中查找给定的x。

如果数组a中的元素与x的值相同，输出相应的下标（下标从0开始）；如果没有找到，输出“Not Found”。

如果输入的n个整数没有按照从小到大的顺序排列，或者出现了相同的数，则输出“Invalid Value”。

1检查数列是否完全递增2不断将x与mid比对，调整缩小left与right的范围3用变量found确定是否找到什么是二分查找二分查找是计算机科学中最基本、最有用的算法之一。

它描述了在有序集合中搜索特定值的过程。

二分查找中使用的术语：目标Target——你要查找的值索引Index——你要查找的当前位置左、右指示符Left，Right——我们用来维持查找空间的指标中间指示符Mid——我们用来应用条件来确定我们应该向左查找还是向右查找的索引它是如何工作的？在最简单的形式中，二分查找对具有指定左索引和右索引的连续序列进行操作。

这就是所谓的查找空间。

二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。

如果查以空的一半结束，则无法满足条件，并且无法找到目标。

注意：二进制搜索可以采用许多替代形式，并且可能并不总是直接搜索特定值。

有时您希望应用特定条件或规则来确定接下来要搜索的哪一侧（左侧或右侧）。

leetCode 704.二分查找给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。

示例1:输入:nums=[-1,0,3,5,9,12],target=9输出:4解释:9出现在nums中并且下标为4示例2:输入:nums=[-1,0,3,5,9,12],target=2输出:-1解释:2不存在nums中因此返回-1提示：你可以假设nums中的所有元素是不重复的。

二分查找的概念二分查找是一种在有序数组中查找目标元素的算法，它的基本思想是每次将数组分成两半，比较中间元素和目标元素，如果相等则返回中间元素的索引，如果不相等则根据大小关系舍弃一半数组，继续在剩下的一半数组中重复这个过程，直到找到目标元素或者数组为空为止。

二分查找的时间复杂度是O(logn)，空间复杂度是O(1)，它是一种高效且简洁的查找算法。

二分查找的实现二分查找可以用递归或者迭代的方式实现，下面我们分别介绍两种实现方法。

递归实现递归实现的核心是定义一个辅助函数，该函数接受四个参数：数组、目标元素、左边界和右边界，表示在数组的左右边界之间查找目标元素。

该函数的逻辑如下：如果左边界大于右边界，说明数组为空，返回-1表示未找到目标元素。

计算中间位置mid = (left + right) / 2，比较数组中的mid位置的元素和目标元素。

如果相等，返回mid表示找到目标元素。

如果不相等，根据大小关系判断目标元素在左半部分还是右半部分，然后递归调用辅助函数，在相应的半部分继续查找。

返回递归调用的结果。

用Python语言实现递归版本的二分查找如下：def binary_search_recursive(arr, target):# 定义一个辅助函数def helper(left, right):# 如果左边界大于右边界，说明数组为空，返回-1if left > right:return-1# 计算中间位置mid = (left + right) //2# 比较中间元素和目标元素if arr[mid] == target:# 如果相等，返回midreturn midelif arr[mid] > target:# 如果中间元素大于目标元素，说明目标元素在左半部分，递归调用辅助函数，在左半部分继续查找return helper(left, mid -1)else:# 如果中间元素小于目标元素，说明目标元素在右半部分，递归调用辅助函数，在右半部分继续查找return helper(mid +1, right)# 调用辅助函数，在整个数组范围内查找return helper(0, len(arr) -1)迭代实现迭代实现的核心是使用一个循环，每次循环都更新左右边界的值，直到找到目标元素或者左右边界交叉为止。