适合二分查找的算法

❶ 二分查找算法

前提要求数据排好序，有递归和非递归版本
int binSearch(const int *Array,int start,int end,int key)
{
int left,right;
int mid;
left=start;
right=end;
while (left<=right) { /注释中为递归算法，执行效率低，不推荐
mid=(left+right)/2;
/* if (key<Array[mid]) {
return(binSearch(Array,left,mid,key));
}
else if(key>Array[mid]){
return (binSearch(Array,mid+1,right,key));
}
else
return mid;
*/
if (key<Array[mid]) {
right=mid-1;
}
else if(key>Array[mid]){
left=mid+1;
}
else
return mid;
}
return -1;
}

❷ 二分查找算法

二分查找算法，该算法要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。如果一个序列是无序的或者是链表，那么该序列就不能使用二分查找。

二分查找算法原理：若待查序列为空，则返回-1，并退出算法；若待查序列不为空，则将它的中间元素与目标数值进行比较，判断是否相等；若相等，则返回中间元素索引，并退出算法；此时已查找成功。若不相等，则比较中间元素与目标数值的大小。

二分查找的一个技巧是：不要出现else，而是把所有情况用else，if写清楚，这样可以清楚地展现所有细节。本文都会使用else，if，旨在讲清楚，读者理解后可自行简化。

❸ python算法：二分查找

二分查找： 又称折半查找 ，输入一个有序的元素列表（必须是有序的）， 将列表中间位置记录的元素与查找元素比较， 如果查找的元素包含在列表中， 则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的元素大于查找元素，则进一步查找前一子表，否则进一步查找后一子表，重复以上过程，直到找到满足条件的记录，使查找成功， 二分查找 返回其位置； 或直到子表不存在为止，此时查找不成功 ，返回None。

二分查找算法要求 ： .必须是有序列表；

二分查找算法时间复杂度： O(log n)

二分查找算法优点： 比较的次数少，查找速度快，平均性能好，占用系统内存较少。

def binary_search(list,item):

low = 0

high = len(list) - 1

while low <= high:

mid = int((low + high)/2) # 整除计算也可用 mid = (low + high)//2

guess = list[mid]

if guess == item:

return mid

if guess < item:

low = mid + 1

else:

high = mid - 1

return None

my_list = [1,3,5,6,8,7,9,12,18,45]

print (binary_search(my_list,2))

print (binary_search(my_list,12))

❹ 二分查找法的具体算法

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解，但是要写一个正确的二分搜索算法也不是一件简单的事。第一个二分搜索算法早在1946年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的着作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的，我们可用C++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函数BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n个升序排列的元素中搜索x,找到x时返回其在数组中的位置，否则返回-1。容易看出，每执行一次while循环，待搜索数组的大小减少一半,因此整个算法在最坏情况下的时间复杂度为O(log n)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。

❺ C#二分查找算法

二分查找的基本思想是：（设R[low..high]是当前的查找区间）
（1）首先确定该区间的中点位置：mid=(low+high)/2
（2）然后将待晌衫闷查的K值与R[mid].key比较：若相等宴弯，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找
//
Source：
public
int
search(int[]
q)
{
int
i,
low
=
0,
high
=
q.Length
-
1,
middle;
Console.Write("请输入想要查找的数字:");
i=int.Parse(Console.ReadLine());
while
(low
<=
high)
{
middle
=
(low
+
high)
/
2;
if
(i
==
q[middle])return
i;
if
(i
<
q[middle])high
=
middle
-
1;
else
low
=
middle
+
1;
}
throw
new
Exception("数组中不存在这个数塌肢。");
}

❻ 基本算法——二分查找算法

    二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

1.条件

（1）必须采用 顺序存储结构 。

（2）必须按关键字大小有序排列。

2.步奏

（1）首先，假设表中元素是按升序排列，将表中间位置记录的 关键字 与查找关键字比较，如果两者相等，则查找成功；

（2）否则利用中间位置 记录 将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表；

（3）重复以上过程，直到找到满足条件的 记录 ，使查找成功，或直到子表不存在为止，此时查找不成功。

3.举例

    有一组元素{1，2，3，4，5，6，7，8，9}，如何查到元素为3。

（1）找到数组中中间元素值5，不等于3，所以把数组分为{1，2，3，4}，{5，6，7，8，9}；

（2）因为5大于3，所以3在前一个数组{1，2，3，4}中查找，中间变量2，3比2大，所以在{3，4}中查询；

（3）查询到3=3，成功。

4.复杂度

     最好的情况下，1次查询成功；最坏的情况下，查询到最后两个数或者最后也查不到相等数，时间复杂度为O(log2n)。

❼ 二分查找算法实现（图解）与实例

当我们要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法，二分查找又叫折半查找。

它对要查找的序列有两个要求，一是该序列必须是有序的（即该序列中的所有元素都是按照大小关系排好序的，升序和降序都可以，本文假设是升序排列的），二是该序列必须是顺序存储的。

如果一个序列是无序的或者是链表，那么该序列就不能进行二分查找。之所以被查找的序列要满足这样的条件，是由二分查找算法的原理决定的。

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

二分查找能应用于任何类型的数据，只要能将这些数据按照某种规则进行排序。然而，正因为它依赖于一个有序的集合，这使得它在处理那些频繁插入和删除操作的数据集时不太高效。这是因为，对于插入和操作来说，为了保证查找过程正常进行，必须保证数据集始终有序。相对于查找来说，维护一个有序数据集的代价更高。此外，元素必须存储在连续的空间中。因此，当待搜索的集合是相对静态的数据集时，此时使用二分查找是最好的选择。

二分查找算法的原理如下：

二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。

二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。

此实现过程的实施是通过变量left和right控制一个循环来查找元素（其中left和right是正在查找的数据集的两个边界值）。

二分查找的时间复杂度取决于查找过程中分区数可能的最大值。对于一个有n个元素的数据集来说，最多可以进行O(㏒₂n)次分区。对于二分查找，这表示最终可能在最坏的情况下执行的检查的次数：例如，在没有找到目标时。所以二分查找的时间复杂度为O(㏒₂n)。

参考：
https://www.html.cn/qa/other/23018.html

https://www.cnblogs.com/idreamo/p/9000762.html