GO语言二分查找算法,详解二分查找算法

Go语言 排序与搜索切片

Go语言标准库中提供了sort包对整型，浮点型，字符串型切片进行排序，检查一个切片是否排好序，使用二分法搜索函数在一个有序切片中搜索一个元素等功能。

关于sort包内的函数说明与使用，请查看

在这里简单讲几个sort包中常用的函数

在Go语言中，对字符串的排序都是按照字节排序，也就是说在对字符串排序时是区分大小写的。

二分搜索算法

Go语言中提供了一个使用二分搜索算法的sort.Search(size,fn)方法：每次只需要比较㏒₂n个元素，其中n为切片中元素的总数。

sort.Search(size,fn)函数接受两个参数：所处理的切片的长度和一个将目标元素与有序切片的元素相比较的函数，该函数是一个闭包，如果该有序切片是升序排列，那么在判断时使用 有序切片的元素 = 目标元素。该函数返回一个int值，表示与目标元素相同的切片元素的索引。

在切片中查找出某个与目标字符串相同的元素索引

完善程序（二分查找法插入元素）

struct list{int key;};/*定义结构类型*/

typedef struct list SeqList,DataType;

void BinInsert(SeqList r[],int *n,DataType x)

{ int low=1,high=*n,mid,i;

while(low=high)

{ mid=(low+high)/2;

if (x.keyr[mid].key)high=mid-1;

else low=mid+1;

}

for(i=*n;i=mid;i--)

r[i+1]=r[i];

r[mid].key=x.key;/*插入元素*/

}

main()

{

SeqList a[11];int i,n;DataType y;

n=0;

for(i=0;i10;i++)/*输入数据*/

{a[i].key=i+1;n++;}

printf("before sort :");

for(i=0;i10;i++)/*排序前的数组*/

{printf("%4d",a[i].key);};

printf("\ninput elem(y)=");/*输入要插入的元素*/

scanf("%d",y.key);

BinInsert(a,n,y);

printf("\nafter sort :");

for(i=0;i11;i++)/*输出排序后的数组*/

printf("%4d",a[i].key);getch();

}

二分查找和快速排序

二分

package stack;

public class HalfSearch {

static int a[]={1,3,5,98,8,9,4,38,12};

public static int halfSeacrh(int[] a,int number){//二分查找

HalfSearch hs=new HalfSearch();

hs.bubbleSort(a);

int startPostion=0;

int endPostion=a.length-1;

int postion=(startPostion+endPostion)/2;

while(startPostionendPostion){

if(a[postion]==number)

return postion;

else if(a[postion]number){

startPostion=postion+1;

}

else if(a[postion]number){

endPostion=postion-1;

}

postion=startPostion+endPostion;

}

return -1;

}

public static void bubbleSort(int a[]){

int temp=0;

for(int i=0;ia.length;i++){

for(int j=i+1;ja.length;j++){

if(a[i]a[j]){

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

}

}

public static void main(String[] args) {

System.out.println(halfSeacrh(a,8));

}

}

快速：templateclass elemtype

void arrayelemtype::sort(int low,int high)

{

if(low=high) return;

int lo=high+1;

elemtype elem=_ia[low];

for( ; ; ) {

while(_ia[++lo]elem lohigh);

while(_ia[--hi]elem hilo);

if(lohi) swap(lo,hi);

else break;

}

swap(low,hi);

sort(low,hi-1);

sort(hi+1,high);

}

对比顺序查找、二分查找和哈希查找算法,它们各自的特点是什么?

顺序查找,二分查找和哈希查找算法,它们各自的特点是：

1.对比顺序查找的特点就是从表的第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功;如果到最后一个元素仍没有目标元素，则查找失败。

2.二分查找的特点就是从表中间开始查找目标元素。如果找到一致元素，则查找成功。如果中间元素比目标元素小，则仍用二分查找方法查找表的后半部分(表是递增排列的)，反之中间元素比目标元素大，则查找表的前半部分。

3.哈希算法的特点是是使用给定数据构造哈希表，然后在哈希表上进行查找的一种算法。先给定一个值，然后根据哈希函数求得哈希地址，再根据哈希地址查找到要找的元素。是通过数据元素的存储地址进行查找的一种算法。

二分查找算法

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

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

若中间元素目标数值，则将当前序列的前半部分作为新的待查序列；若中间元素目标数值，则将当前序列的后半部分作为新的待查序列；在新的序列上重新从第（1）步开始查找。

二分法查找的思路：首先，从数组的中间元素开始搜索，如果该元素是目标元素，则搜索过程结束，否则执行下一步。如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。如果某一步数组为空，则表示找不到目标元素。

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

二分查找法的具体算法

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

templateclass 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 (xa[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)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。