作者：hacker发布时间：2022-07-08分类：黑客教程浏览：154评论：5
//折半查找
#includestdio.h
/*利用不对称边界+下标法进行二分法查找，所用数组为升序排序*/
int binarySearch(int a[],int n,int x)
{
int low=0,high=n,mid; /*low为待查元素可能范围的第一个元素的下标、high为待查元素可能范围后第一个元素的下标*/
while(lowhigh) /*千万不要取等号，取等号就错了*/
{
mid=(high+low)/2;
if(a[mid]==x)
return mid;
else
{
if(a[mid]x)
high=mid; /*前半段找*/
else
low=mid+1; /*后半段找*/
}
}
return -1; /*返回-1表示未找到*/
}
void main()
{
int i,x,a[]={1,2,3,4,5},find;
printf("please input num for search:\n");
scanf("%d",x);
find=binarySearch( a,5,x);
if(find!=-1)
printf("the search's element is %d at %dth in arry\n",a[find],find);
else
printf("not found\n");
}
此法若判断循环结束时用了等于号即：low=high，当输入0时就陷入了死循环，二当输入数据不在数组中是，又会出现逻辑错误。因为这是用不对称边界进行二分法查找。
#includestdio.h
/*利用不对称边界+指针法进行二分法查找，所用数组为升序排序*/
int* binarySearch(int a[],int n,int x)
{
int *low=a[0],*high=a[n],*mid=NULL; /*low为待查元素可能范围的第一个元素的指针、high为待查元素可能范围后第一个元素的指针*/
while(lowhigh) /*千万不要取等号，取等号就错了*/
{
mid=low+(high-low)/2; /*不能用(low+high）/2代替*/
if(*mid==x)
return mid;
else
{
if(*midx)
high=mid; /*前半段找*/
else
low=mid+1; /*后半段找*/
}
}
return NULL; /*返回NULL表示未找到*/
}
void main()
{
int i,x,a[]={1,2,3,4,5},*find;
printf("please input num for search:\n");
scanf("%d",x);
find=binarySearch( a,5,x);
if(find!=NULL)
printf("the search's element is %d at %dth in arry\n",*find,find-a);
else
printf("not found\n");
}
比较：利用对称边界进行二分法查找：
1、
#includestdio.h
/*利用对称边界+下标法进行二分法查找，所用数组为升序排序*/
int binarySearch(int a[],int n,int x)
{ //此时若把high=n;则可会成为不安全代码，如：到待插找元素大于所有元素时，他会读取a[n]的值，这里出现了下标越界的危险
int low=0,high=n-1,mid; /*low为待查元素可能范围的第一个元素的下标、high为待查元素可能范围的最后一个元素下标*/
while(low=high) /*记得要取等号，不取等号就错了*/
{
mid=(high+low)/2;
if(a[mid]==x)
return mid;
else
{
if(a[mid]x)
high=mid-1; /*前半段找*/
else
low=mid+1; /*后半段找*/
}
}
return -1; /*返回-1表示未找到*/
}
void main()
{
int i,x,a[]={1,2,3,4,5},find;
printf("please input num for search:\n");
scanf("%d",x);
find=binarySearch( a,5,x);
if(find!=-1)
printf("the search's element is %d at %dth in arry\n",a[find],find);
else
printf("not found\n");
}
2、
#includestdio.h
/*利用不对称边界+指针法进行二分法查找，所用数组为升序排序*/
int* binarySearch(int a[],int n,int x)
{
int *low=a[0],*high=a[n],*mid=NULL; /*low为待查元素可能范围的第一个元素的指针、high为待查元素可能范围后第一个元素的指针*/
while(low=high) /*记得要取等号，不取等号就错了*/
{
mid=low+(high-low)/2;
if(*mid==x)
return mid;
else
{
if(*midx)
high=mid+1; /*前半段排序*/
else
low=mid+1; /*后半段排序*/
}
}
return NULL; /*返回NULL表示未找到*/
}
void main()
{
int i,x,a[]={1,2,3,4,5},*find;
printf("please input num for search:\n");
scanf("%d",x);
find=binarySearch( a,5,x);
if(find!=NULL)
printf("the search's element is %d at %dth in arry\n",*find,find-a);
else
printf("not found\n");
}
对有序链表一般不能用二分法查找，但简单链表还是用二分法查找还是容易解决，复杂链表只是稍微复杂点，我想还是能解决的，因为我写出了一个程序：
#includestdio.h
#includelimits.h
typedef struct staticLink{
int data;
struct staticLink *next;
}myStaticLink;
/*利用不对称边界+指针法对”链表“进行二分法查找*/
myStaticLink* binarySearch(myStaticLink *head,int n,int x)
{
int i,n_low=0,n_high=n,n_mid=0,pos;
myStaticLink *low=head,*mid=head,*high=head; /*low为待查元素可能范围的第一个元素的指针、high为待查元素可能范围后第一个元素的指针*/
for(i=0;in;i++) /*经过n-1次把high定位到链表的最后一个元素的next域，即NULL*/
high=high-next;
while(low-data((high==NULL)?INT_MAX:high-data) low!=NULL) /*此等式是模拟指针法中lowhigh*/
{
pos=(n_high+n_low)/2;
for(i=0;ipos;i++)
{
mid=mid-next;
n_mid++;
}
if(mid-data==x)
return mid;
else
{
if(mid-datax)
{
high=mid; /*前半段排序*/
mid=head;
n_high=n_mid;
n_mid=0;
}
else
{
low=mid-next; /*后半段排序*/
mid=head;
n_low=n_mid+1;
n_mid=0;
}
}
}
return NULL; /*返回NULL表示未找到*/
}
void main()
{
int position=0,x; /*position 用于记录待找数据在链表中的位置*/
myStaticLink *pos,*find,*head,a,b,c,d; /*pos 用于以后计算待找数据在链表中的位置*/
pos=head=a; /*初始化静态链表的节点a,b,c,d*/
a.data=1;
a.next=b;
b.data=2;
b.next=c;
c.data=3;
c.next=d;
d.data=4;
d.next=NULL;
printf("please input num for search:\n");
scanf("%d",x);
find=binarySearch(head,4,x);
while(pos!=find)
{
pos=pos-next;
position++;
}
if(find!=NULL)
printf("the search's element is %d at %dth in arry\n",find-data,position);
else
printf("not found\n");
}
//插入排序
插入排序
/*small to big*/
/*从a[1]开始控制n-1趟插入循环，比待插元素大的后移*/
#include stdio.h
void insertsort ( int a[],int n)
{
int i,j,temp;
for(i=2;i=n;i++){
temp=a[i];
j=i-1;
while(j0 a[j]temp)
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}
void main()
{
int a[6]={-111,1,2,5,3,4},i=1; /*丢弃a[0],排序从a[1]开始*/
printf("before insertsort arry's element is:\n");
for(i=1;i6;i++)
printf("%3d",a[i]);
printf("\n");
insertsort(a,5);
printf("after insertsort arry's element is:\n");
for(i=1;i6;i++)
printf("%3d",a[i]);
printf("\n");
}
/*big to small*/
/*从a[n-1]开始控制n-1趟插入循环，比待插元素大的前移*/
/*big to small，笨蛋改法，只需把a[j]temp改成a[j]temp就可*/
#include stdio.h
void insertsort ( int a[],int n)
{
int i,j,temp;
for(i=n-1;i=1;i--){
temp=a[i];
j=i+1;
while(j=n a[j]temp)
{
a[j-1]=a[j];
j++;
}
a[j-1]=temp;
}
}
void main()
{
int a[6]={-111,1,2,0,3,4},i=1; /*丢弃a[0],排序从a[1]开始*/
printf("before insertsort arry's element is:\n");
for(i=1;i6;i++)
printf("%3d",a[i]);
printf("\n");
insertsort(a,5);
printf("after insertsort arry's element is:\n");
for(i=1;i6;i++)
printf("%3d",a[i]);
printf("\n");
}
2、不对称下标法insertsort排序，没必要对其a[0]
#includestdio.h
/*不对称法实现insertsort,small to big*/
/*arg:n维数组元素个数*/
void insertSort(int a[],int n)
{
int i,j,temp;
for(i=1;in;i++)
{
temp=a[i];
j=i-1;
for(;j=0 a[j]temp;j--)
a[j+1]=a[j];
a[j+1]=temp;
}
}
void main()
{
int i,a[5]={1,3,4,2,5};
printf("before insertsort the arry's element is\n");
for(i=0;i5;i++)
printf("%3d",a[i]);
printf("\n");
insertSort(a,5);
printf("after insertsort the arry's element is\n");
for(i=0;i5;i++)
printf("%3d",a[i]);
printf("\n");
}
若要实现big to small 只需把a[j]temp 改成a[j]temp就可。
//希尔排序
1、 用bubble排序子序列实现shellsort
#includestdio.h
/*shell sort,small to big*/
void shellSort(int a[],int n)
{
int i,j,gap=n,flag,temp;
while(gap1)
{
flag=1;
gap/=2;
do{
for(i=0;in-gap;i++) /*一定不要写成for(i=0;in-gap flag;i++*/
{
flag=0;
j=i+gap;
if(a[i]a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
flag=1;
}
}
}while(flag==1);
}
}
void main()
{
int i,a[5]={1,3,4,2,5};
printf("before shellsort the arry's element is\n");
for(i=0;i5;i++)
printf("%3d",a[i]);
printf("\n");
shellSort(a,5);
printf("after shellsort the arry's element is\n");
for(i=0;i5;i++)
printf("%3d",a[i]);
printf("\n");
}
//冒泡排序
1./*改进冒泡排序法*/
#includestdio.h
void bubbleSort(int arry[],int n)
{ /*由小到大排序*/
int i,j,flag=1,temp;
for(i=0;in-1 flag==1;i++)
{/*先确定后面的*/
flag=0;
for(j=i;jn-1;j++) /*这里错本程序输出正确恰好是一种凑巧,这里应改为for(j=0;jn-i-1;j++)*/
if(arry[j]arry[j+1])
{
temp=arry[j];
arry[j]=arry[j+1];
arry[j+1]=temp;
flag=1;
}
}
}
void main()
{
int a[]={1,2,3,7,4,5};
int i;
bubbleSort(a,6);
for(i=0;i6;i++)
printf("%3d",a[i]);
printf("\n");
}
bubble sort 中，先确定后面的，用for(j=0;jn-i-1;j++) 即从前面往后下沉或冒泡。 若要先确定前面的，可以用
for(j=n-1;j=i;j--)
{ /*由小到大排序*/
if(arry[j]arry[j-1])
{
temp=arry[j];
arry[j]=arry[j-1];
arry[j-1]=temp;
}
}
2.改进冒泡排序
#includestdio.h
int combsort(int p[],int n)
{/*改进冒泡有大到小排序*/
int op=0;
int i,temp,gap=n, flag=1;
while(gap1 || flag!=0)
{
flag=0;
gap=(gap==9 || gap==10)?11:gap*10/13;
if(gap==0)
gap=1;
for(i=n-1;i-gap=0;i--)
{
if(p[i]p[i-1])
{
temp=p[i];
p[i]=p[i-1];
p[i-1]=temp;
flag=1;
}
op++;
}
}
return op;
}
void main()
{
int i;
int arry[10]={1,3,4,2,5,6,7,9,8,0};
combsort(arry,10);
for(i=0;i10;i++)
printf("%d ",arry[i]);
printf("\n");
}
想知道跟多，把你的邮箱发给我，我把它发给你
首先你的二分查找算法模型是错的，因为它并没有体现出高位指针与低位指针是否已超过重合点？如果超过时就结束查找。你应该这样写：
Java语言：
public static void main(String[] args){
int array[]={1,2,3,4,5};
System.out.println(binarySearch(array, 3)); // print 2
System.out.println(binarySearch(array, 100)); // print -1
}
/**
* 折半搜索算法
* @param array 有序线性数组
* @param findValue 要搜索的值
* @return 返回目标值所在数组的下标
*/
static int binarySearch(int[] array,int findValue){
int low,high,middle;
low=0; // 低位指针位置
high=array.length-1; // 高位指针位置
while(low=high){ // 指针是已超过重合点?
middle=(low+high)/2;// 定位到中间
if(findValuearray[middle]) high=middle-1; // 向低位靠拢
else if(findValuearray[middle]) low=middle+1;// 向高位靠拢
else return middle; // 找到了
}
return -1; // 没有找到
}
C#语言：
static void Main(string[] args)
{
int[] array={1,2,3,4,5};
Console.WriteLine(BinarySearch(array, 3)); // print 2
Console.WriteLine(BinarySearch(array, 100));// print -1
Console.ReadKey(true);
}
/// summary
/// 折半搜索算法
/// /summary
/// param name="array"有序线性数组/param
/// param name="findValue"要搜索的值/param
/// returns返回目标值所在数组的下标/returns
static int BinarySearch(int[] array, int findValue)
{
int low, high, middle;
low = 0; // 低位指针位置
high = array.Length - 1; // 高位指针位置
while (low = high) // 指针是已超过重合点?
{
middle = (low + high) / 2;// 定位到中间
if (findValue array[middle]) high = middle - 1; // 向低位靠拢
else if (findValue array[middle]) low = middle + 1;// 向高位靠拢
else return middle; // 找到了
}
return -1; // 没有找到
}
什么是二分查找？
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二分查找优缺点
优点是比较次数少，查找速度快，平均性能好；
其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
使用条件：查找序列是顺序结构，有序。
过程
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
利用循环的方式实现二分法查找
public class BinarySearch {
public static void main(String[] args) {
// 生成一个随机数组 int[] array = suiji();
// 对随机数组排序 Arrays.sort(array);
System.out.println("产生的随机数组为： " + Arrays.toString(array));
System.out.println("要进行查找的值： ");
Scanner input = new Scanner(System.in);
// 进行查找的目标值 int aim = input.nextInt();
// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);
}
/** * 生成一个随机数组 *
* @return 返回值，返回一个随机数组 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之间的随机数 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循环遍历为数组赋值 for (int i = 0; i array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}
/** * 二分法查找 ---循环的方式实现 *
* @param array 要查找的数组 * @param aim 要查找的值 * @return 返回值，成功返回索引，失败返回-1 */
private static int binarySearch(int[] array, int aim) {
// 数组最小索引值 int left = 0;
// 数组最大索引值 int right = array.length - 1;
int mid;
while (left = right) {
mid = (left + right) / 2;
// 若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围 if (aim array[mid]) {
right = mid - 1;
// 若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围 } else if (aim array[mid]) {
left = mid + 1;
// 若查找数据与中间元素值正好相等，则放回中间元素值的索引 } else {
return mid;
}
}
return -1;
}}
运行结果演示：
由以上运行结果我们得知，如果要查找的数据在数组中存在，则输出该数据在数组中的索引；如果不存在则输出 -1 ，也就是打印 -1 则该数在数组中不存在，反之则存在。
四、利用递归的方式实现二分法查找
public class BinarySearch2 {
public static void main(String[] args) {
// 生成一个随机数组 int[] array = suiji();
// 对随机数组排序 Arrays.sort(array);
System.out.println("产生的随机数组为： " + Arrays.toString(array));
System.out.println("要进行查找的值： ");
Scanner input = new Scanner(System.in);
// 进行查找的目标值 int aim = input.nextInt();
// 使用二分法查找 int index = binarySearch(array, aim, 0, array.length - 1);
System.out.println("查找的值的索引位置： " + index);
}
/** * 生成一个随机数组 * * @return 返回值，返回一个随机数组 */
private static int[] suiji() {
// Random.nextInt(n)+m 返回m到m+n-1之间的随机数 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循环遍历为数组赋值 for (int i = 0; i array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}
/** * 二分法查找 ---递归的方式 * * @param array 要查找的数组 * @param aim 要查找的值 * @param left 左边最小值 * @param right 右边最大值 * @return 返回值，成功返回索引，失败返回-1 */
private static int binarySearch(int[] array, int aim, int left, int right) {
if (aim array[left] || aim array[right]) {
return -1;
}
// 找中间值 int mid = (left + right) / 2;
if (array[mid] == aim) {
return mid;
} else if (array[mid] aim) {
//如果中间值大于要找的值则从左边一半继续递归 return binarySearch(array, aim, left, mid - 1);
} else {
//如果中间值小于要找的值则从右边一半继续递归 return binarySearch(array, aim, mid + 1, array.length-1);
}
}}
运行结果演示：
总结：
递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~
二分查找 看名字 理解意思就是
每次把你需要查找的数组分成基本平均的2部分，然后看两部分中间的那个数是不是我们要找的数。假如不是我们要找的数，那么我们看这个数是比我们的大呢还是比我们要找的数小，假如说中间这个数比我们要找的数小 那么我们要找的数是不是应该在比较大的那一部分，如果中间这个数比我们要找的数更大，那么我们要找的数应该是在比较小的那一部分的。
然后继续按照我们刚才的方法来处理刚才挑选出来的这一个部分，最不理想的情况就是：你最后把这个数组已经分到了最小的部分（一个部分就只有一个数值的时候）了，那么这个时候你一比较 就知道最后这个数就是我们要找的数了（当然 也有可能根本找不到我们要找的那个数，这种时候 说明我们这个数组里面根本就没有我们要找的这个数）。
OK了吗？
再给你举个例子吧
我们现在有一个已经排序好了的数组（顺序表） 如下
1 2 3 5 8 9 12 45 69 85 99 102 103
这个数组总共有13个数字（如果我没有数错的话）
现在我们要在其中找到5这个数字
那么我们首先把这个数组分成两个部分（以最中间的那个数为界限）我们用这个数组的长度13/2=6.5 进一法 取值为7
所以我们把第七个元素作为我们这一轮的判断标准
第七个元素=12
我们拿5（要查找的数） 和12（中间数）比较，发现5比12小 所以我们要找的数字应该是在我们12的前面的
那我们现在就只需要对1-6这六个元素进行刚才的过程了
1-6总共包含了6个元素 我们用刚才的方法取出一个值来进行比较
6/2=3 这里进一法不起作用了
我们把3号元素作为我们查找的对比项
比较5 （要查找的数）和3号元素3（中间数也就是比较项）进行比较 发现53 所以我们知道我们要找的数应该是在这个范围内 3的后面的
所以现在我们可以进一步确定我们要找的数的范围是 4-6这个范围了
那么我们在4-6这个范围进行查找 共3项 3/2=1.5 进一法为2 所以我们以这个范围内第二个项为中间项进行比较 也就是第5项 数值为8 我们比较5和8 发现5比8更小
所以我们确定我们要找的数应该在4-4这个范围内 （虽然说我们人是可以判断了 但是计算机还不行哦 我们这些程序都是给计算机用的 所以我们下面的步骤还得进行下去）
4-4这个范围内总共有一项 1/2=0.5 进一法为1
所以我们确定要作比较的项应该为这个范围内的第一项 也就是第四项 数值取出来为5 拿5（要找的数值）和5（中间项）进行比较 发现5=5 此时说明我们本次查找的目的达到了 找到了相同的项 我们的查找就此结束
就此推论 你可以想象
应该可以总结一张表出来
查找数组总个数 需要查找的最多次数
1个 1
2-3个 2
4-7个 3
8-15个 4
16-31个 5
32-63个 6
………………………………………………………………
（如果你通过此次回答解决问题 希望你采纳答案 如果没解决 请继续在这里发问 如果是成都本地的 可以在这里留言说是成都本地人 可以来我家教中心 我当面给你讲（讲这个不收费））
一、顺序查找
条件：无序或有序队列。
原理：按顺序比较每个元素，直到找到关键字为止。
时间复杂度：O(n)
二、二分查找（折半查找）
条件：有序数组
原理：查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。
时间复杂度：O(logn)
三、哈希表（散列表）
条件：先创建哈希表（散列表）
原理：根据键值方式(Key value)进行查找，通过散列函数，定位数据元素。
时间复杂度：几乎是O(1)，取决于产生冲突的多少。
标签：二分查找定位
已有5位网友发表了看法：
访客 评论于 2022-07-08 22:26:01 回复
er insertsort the arry's element is\n"); for(i=0;i5;i++) printf("%3d",a[i]); printf("\n");}若要实现big
访客 评论于 2022-07-09 04:58:22 回复
了我们把3号元素作为我们查找的对比项比较5 （要查找的数）和3号元素3（中间数也就是比较项）进行比较 发现53 所以我们知道我们要找的数应该是在这个范围内 3的后面的所以现在我们可以进一步确定我们要找的数的范围是 4-6这个范围了那么我们在4-6
访客 评论于 2022-07-09 01:56:06 回复
int n,int x){ //此时若把high=n;则可会成为不安全代码，如：到待插找元素大于所有元素时，他会读取a[n]的值，这里出现了下标越界的危险 int low=0,high=n-1,mid; /*low为待查元素可能
访客 评论于 2022-07-08 22:41:21 回复
.out.println("产生的随机数组为： " + Arrays.toString(array));System.out.println("要进行查找的值： ");Scanner input = new Scanner(System.in);// 进行查找的目标值 int aim
访客 评论于 2022-07-09 03:37:03 回复
w)/2; /*不能用(low+high）/2代替*/ if(*mid==x) return mid; else { if(*midx) high=mid; /*前半段找*/ else low=mid+1; /*后半段