去创新工厂做了一下笔试题,发现一个二分查找也竟然写错,真服了。
现在再补上吧。
我把最终的要求简化一下。要求是:在一个升序的序列中,找出满足 第一个 不小于(大于或者等于)待查找元素 在数组中的位置。
如: 如果数组是 2, 4, 6, 8 (数组下标从0开始),要查找3时,此时就要返回4 在数组中的位置了
下面是简单的程序实现
#include <stdio.h>
///////////////////////////////////////////////////////////////////
// 功能描述:二分查找, 数组是按照升序排序的, 返回数组中第一个
// 不小于待查找元素的 的位置
// 如: 2, 4, 6 , 9 如果查找 5 , 则返回2 (下标从0开始)
// 输入参数:
// a:查找数组的指针
// n:指针a指向的数组的元素个数
// search:待查找的元素(要求 search >0 && search <= a[n-1])
// 输出参数:
// 无
//
// 返回值:
// -1:search范围有误
// 返回第一个不小于待查找元素在数组中的位置
//
////////////////////////////////////////////////////////////////////
int mid_search(int *a, int n, int search)
{
if (search<0 || search>a[n-1])
return -1;
int low = 0, high = n-1;
int middle = 0;
while (low<=high){
middle = (low+high)/2;
if (a[middle]==search)
return middle;
if (a[middle]<search)
low = middle + 1;
else
high = middle - 1;
}
return low;
}
//main 测试
int main()
{
int a[10] = {2, 10, 20, 30, 40, 50, 60, 70, 80, 90};
int search_num[5] = {-1, 1, 100, 50, 66};
int i = 0, res = 0;
for (i=0; i<10; i++){
printf("%d",a[i]);
if (i<9)
printf("\t");
}
printf("\n");
for (i=0; i<5; i++){
printf("%d \t", search_num[i]);
res = mid_search(a, 10, search_num[i]);
printf("%d\n", res);
}
return 0;
}
其实,这个地方的着急就在于,当待查找的元素和数组中的元素不相等的时候,那么返回的位置是哪个? low? high? or..
其实当待查找元素在数组中不存在时,最后一次循环 low 和 high 最终会指向同一元素, 此时我们将所有的元素可以分为三部分 a[0]---a[low-1], a[low](a[high]), a[low+1]--a[n-1], (middle,low 和 high 指向同一元素)。
由于循环我们可以知道, search_num (待查找元素) 肯定是大于 a[0]---a[low-1], 肯定小于 a[low+1]--a[n-1], 所以我们要找的结果,要么是目前的low的位置,或者就是low+1的位置(看a[low]和search的大小)。
1) 相等的情况不说了
2) a[low] > search 时,此时目前的low 就是我们需要的位置,看循环的执行,此时是把high的值改变,low的值没变,所以循环结束的low值就是要返回的结果.
3) a[low] < search 时, 应该返回的是 目前的 low+1的位置,那看循环执行是将 low = middle+1(low==middle). 所以循环结束时的low值即为要找的位置。
好了,我们返回low值就可以了。
分享到:
相关推荐
折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)
二分查找算法,二分查找算法课件,二分查找算法PPT
二分查找_测试
二分查找算法
简单地实现了二分查找的可视化。界面很简单就包括两个部分:界面左侧是可视化查找部分,右侧是二分查找的代码。 程序的关键点主要有两点: 1. 如何在页面上表示出查找程序的运行过程。 2. 如何将排序程序的运行...
1.二分查找又称为折半查找,它要求要查找的顺序表必须是有序表,即表中结点按关键字有序.并且要用顺序存储结构。 基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则...
二分查找 C语言语言源代码 用递归写的 C语言入门经典代码 值得收藏
//二分查找 #include const int MAXN=10010; using namespace std; //二分查找,递归实现 int binarySearch(int a[],int low,int high,int key) { //查找某元素是否在数组中,若存在,则返回下标,否则...
二分查找
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表...
二分查找
VB 二分查找 VB 二分查找 VB 二分查找
s[middle] 关键字小于中值 继续二分查找 并将上限改为middle BinarySearch s x low middle 1 ; else 关键字大于中值 继续二分查找 并将下限改为middle BinarySearch s x middle + 1 high ;">if high < low ...
二分查找ppt
一、实验目的: 熟悉各种查找算法及其复杂性,能够根据实际情况选择合适的存储结构。 二、实验要求: 1、掌握查找的基本方法。 2、提交实验报告,报告...编程分别对有序顺序表的顺序查找,二分查找算法进行实现。
int BinSearch(SeqList R,int n,KeyType k) /*二分查找算法*/ { int low=0,high=n-1,mid,count=0; while (low) { mid=(low+high)/2; printf("第%d次查找:在[%d,%d]中查找到元素R[%d]:%d\n",++count,low,high,...
文件读出数组进行选择排序和二分查找文件读出数组进行选择排序和二分查找java实现
设计一个程序,建立由有序序列R[0..n-1]进行二分查找产生的判定树,在此基础上完成如下功能: (1) 输出n=11时的判定树并求成功情况下的平均查找长度ASl (2) 通过构造判定树可以求得的成功情况下的平均查找长度...
C++ 二分查找法