首先申明,二分法查找只适用与已排序的数列,如果是混乱数列。。我也无能为力~
有一个数组 v 已经按升序排列了,数组 v 有 n=20 个元素。数组中有个元素 x,如何知道 x 位于该数组的第几位呢?
解决这个问题的一个普遍方法是二分法查找。下面是程序:
#include <stdio.h>
int binsearch(int x, int v[], int n);
main()
{
int i, result, n;
int wait;
int x = 17; // 需要查找的数值
int v[19]; // 定义一个数组
// 给数组赋值
for(i = 0; i < 20; ++i)
v[i] = i;
/**
for(i = 0; i < 20; ++i)
printf("%d \n", v[i]);
*/
n = 20;
result = binsearch(x, v, n);
printf("%d", result);
scanf("%d", &wait);
}
int binsearch(int x, int v[], int n)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high)
{
mid = (low + high) / 2;
if(x < v[mid])
high = mid - 1;
else if (x > v[mid])
low = mid + 1;
else
return mid;
// 看看循环执行了多少次
printf("mid = %d, low = %d, high = %d \n", mid, low, high);
}
return -1;
}
思路很简单:首先将输入值 x 与数组 v 的中间元素比较,如果 x 小于中间的元素,则将 high 值设为 中间元素-1,同理,若 x 大于中间元素,则将中间元素 + 1作为 low,再在low 与 high之间进行查找
二分法插入排序
算法思想简单描述:
在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们
中间的那个元素比,如果小,则对前半再进行折半,否则对后半
进行折半,直到left>right,然后再把第i个元素前1位与目标位置之间
的所有元素后移,再把第i个元素放在目标位置上。
二分法没有排序,只有查找。所以当找到要插入的位置时。移动必须从最后一个记录开始,向后移动一位,再移动倒数第2位,直到要插入的位置的记录移后一位。
二分插入排序是稳定的,平均时间O(n2)
void binsort(ref int[] data1)
1、二分法查找插入位置
如果R[i]<R[m]成立,那右指针就要向左移动中间指针一位,否则,左指针要向左移动中间指针一位。反复查找,直到左指针大于右指针时停止。
2、后移,有点迷惑,什么时候需要后移呢?有哪些记录需要移动呢?
虽然我们很清楚的知道,我们需要后移那些排序码大于R[i]的记录,但难免会问自己这样几个问题。其实它相当于需要移动从i-1到左指针的记录。
3、插入
由1中得到的左指针其实就是元素要插入的位置。
4、算法
{
int left,right,num;
int middle,j;
for( int i = 1;i < data1.Length;i++)
{
// 准备
left = 0;
right = i-1;
num = data1[i];
// 二分法查找插入位置
while( right >= left)
{
// 指向已排序好的中间位置
middle = ( left + right ) / 2;
if( num < data1[middle] )
// 插入的元素在右区间
right = middle-1;
else
// 插入的元素在左区间
left = middle+1;
}
// 后移排序码大于R[i]的记录
for( j = i-1;j >= left;j-- )
{
data1[j+1] = data1[j];
}
// 插入
data1[left] = num;
}
// 插入的元素在左区间
left = middle+1;
}
// 后移排序码大于R[i]的记录
for( j = i-1;j >= left;j-- )
{
data1[j+1] = data1[j];
}
// 插入
data1[left] = num;
}
/* 二分法插入排序的算法源程序*/
#include<stdio.h>
#define MAXNUM 100
typedef int KeyType;
typedef int DataType;
typedef struct {
KeyType key; /* 排序码字段 */
/*DataType info; 记录的其它字段 */
} RecordNode;
typedef struct {
int n; /* n为文件中的记录个数,n<MAXNUM */
RecordNode record[MAXNUM];
} SortObject;
void binSort(SortObject * pvector) { /* 按递增序进行二分法插入排序 */
int i, j, left, mid, right;
RecordNode temp;
RecordNode *data = pvector->record;
for( i = 1; i < pvector->n; i++ ) {
temp = data[i];
left = 0; right = i-1; /* 置已排序区间的下、上界初值 */
while (left <= right) {
mid = (left + right)/2; /* mid指向已排序区间的中间位置 */
if (temp.key < data[mid].key)
right = mid-1; /* 插入元素应在左子区间 */
else left = mid+1; /* 插入元素应在右子区间 */
}
for (j = i-1; j >= left; j--)
data[j+1] = data[j]; /* 将排序码大于ki的记录后移 */
if (left != i) data[left] = temp;
}
}
SortObject vector={10, 49,38,65,97,76,13,27,49,50,101};
int main(){
int i;
binSort(&vector);
for(i = 0; i < vector.n; i++)
printf("%d ", vector.record[i]);
getchar();
return 0;
}
。
分享到:
相关推荐
binary sort,二分法查找,binary search, 二分法排序,merge sort 混合排序,shell sort 希尔排序,insertion sort 插入排序。数据结构 data structure
C语言实现的二分法快速查找|二分法排序|二分法查找C#
二分法排序和查找(C#)
适合有点基础的人使用,于软件水平考试,计算机等级考试等复习使用
冒泡排序、快速排序和二分法查找的分析 Java
二分法查找和顺序查找 排序后二分法
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
但是,二分法查找要求数组必须是有序的,如果数组无序,则需要先进行排序操作。 总之,二分法查找是一种常用的查找算法,适用于有序数组中查找某个元素的位置。通过将待查找区间缩小一半的方式,可以快速地定位目标...
初学java的基础算法,巩固学习,面试常考的基础算法,自己面试被问了几次,所以总结出来给大家分享!!!!
是直接插入算法的改进 查找位置使用的是二分法
java 二分法查找案例与数组排序案例
初始化一个已排序的整型数组,用二分法查找其中是否存在常量5,如有,打印其下标。
Java常用高效8大排序算法与二分法查找,适合正在学习算法和准备学习算法的算法爱好者和研究使用算法的开发人员使用。
c++二分法查找,先进行冒泡排序后查找 int main() { int num[100]; int ncount; while (1) { cout输入数据元素个数(输入非正数即退出程序):"; cin>>ncount; if(ncount) exit(1); Input(num,ncount); //...
设计函数能够用二分法查找元素对应下标,同时可以检测出用户是否输入有误,鲁棒性较好。
欢迎下载,资源共享。c语言实现。排序方法
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找(同步到博客).doc
主要介绍了Java使用二分法进行查找和排序的示例,二分插入排序和二分查找是基础的算法,需要的朋友可以参考下
c#练习二分法示例二分法查找是一种非常高效的搜索方法,主要原理是每次搜索可以抛弃一半的值来缩小范围。其时间复杂度是O(log2n),一般用于对普通搜索方法的优化。 二分法的适用情况一般满足以下几点:(1)该数组...
本人用vb.net编写的二分法查找程序,不同于常规二分法,本二分法适合与在对海量数据排序下的快速查找。非常实用。