编程实现在一维数组中的折半查找算法。以上可采用任何编程语言实现.
发布网友
发布时间：2022-11-30 03:33
共5个回答
热心网友
时间：2023-10-30 08:37
将要查找的数据项与数组的中间元素相比较。
如果它们相同，那么查找成功。
如果查找的数据项小于数组的中间元素，那么就放弃数组的后半部分。
如果查找的数据项大于数组的中间元素，那么就放弃数组的前半部分。
重复步骤1～4，将数组不断减半，直至找到查找的数据项或者查找完整个数组为止。
从下面的程序清单可以看出，折半查找算法在实际应用中几乎不受数组大小的影响，即使数组的长度增加一倍，也只是在程序中多了一次循环而已。
'
' Description: Mole containing various binary search routines
'
' Authors: Stephen Bullen, www.oaltd.co.uk
' Rob Bovey, www.appspro.com
'
Option Explicit
Option Private Mole
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' Comments: Uses a binary search algorithm to quickly locate a string
' within a sorted array of strings
'
' Arguments: sLookFor The string to search for in the array
' auArray An array of strings, sorted in ascending order
' lCompareMethod Either vbBinaryCompare or vbTextCompare. Defaults to vbTextCompare
' lNotFound The value to return if the text isn't found. Defaults to -1
'
' Returns: Long The located position in the array, or -1 if not found
'
' Date Developer Action
' --------------------------------------------------------------
' 02 Jun 04 Stephen Bullen Created
'
Function BinarySearchString(ByRef sLookFor As String, ByRef asArray() As String, _
Optional ByVal lCompareMethod As VbCompareMethod = vbTextCompare, _
Optional ByVal lNotFound As Long = -1) As Long
Dim lLow As Long, lMid As Long, lHigh As Long
Dim iComp As Integer
On Error GoTo PTR_Exit
'Assume we didn't find it
BinarySearchString = lNotFound
'Get the starting positions
lLow = LBound(asArray)
lHigh = UBound(asArray)
Do
'Find the midpoint of the array
lMid = (lLow + lHigh) \ 2
'Compare the mid-point element to the string being searched for
iComp = StrComp(asArray(lMid), sLookFor, lCompareMethod)
If iComp = 0 Then
'We found it, so return the location and quit
BinarySearchString = lMid
Exit Do
ElseIf iComp = 1 Then
'The midpoint item is bigger than us - throw away the top half
lHigh = lMid - 1
Else
'The midpoint item is smaller than us - throw away the bottom half
lLow = lMid + 1
End If
'Continue until our pointers cross
Loop Until lLow > lHigh
PTR_Exit:
End Function
'********************************************************************
'* Function Name: BinarySearchVariant
'*
'* Inputs: vLookFor - The value to search for in the array
'* vaArray - A Variant array, sorted in ascending order
'* lNotFound - The value to return if the text isn't found
'* Defaults to -1
'*
'* Outputs: The located position in the array, or -1 if not found
'*
'* Purpose: Uses a binary search algorithm to quickly locate a string
'* within a sorted array of strings
'*
'********************************************************************
Function BinarySearchVariant(ByVal vLookFor As Variant, ByRef vaArray As Variant, _
Optional ByVal lNotFound As Long = -1) As Long
Dim lLow As Long, lMid As Long, lHigh As Long
On Error GoTo PTR_Exit
'Assume we didn't find it
BinarySearchVariant = lNotFound
'Get the starting positions
lLow = LBound(vaArray)
lHigh = UBound(vaArray)
Do
'Find the midpoint of the array
lMid = (lLow + lHigh) \ 2
If vaArray(lMid) = vLookFor Then
'We found it, so return the location and quit
BinarySearchVariant = lMid
Exit Do
ElseIf vaArray(lMid) > vLookFor Then
'The midpoint item is bigger than us - throw away the top half
lHigh = lMid - 1
Else
'The midpoint item is smaller than us - throw away the bottom half
lLow = lMid + 1
End If
'Continue until our pointers cross
Loop Until lLow > lHigh
PTR_Exit:
End Function
参考资料：http://www.myfootprints.cn/blog/post/74.html
热心网友
时间：2023-10-30 08:37
* 文件名称:test_halfind.c
* 摘 要:折半查找法
* 作 者:E_rainboy
* 完成时间:2009年3月29日
*
*/
#include <stdio.h>
#include <assert.h>
#define LEN 8
int a[LEN] = { 1, 3, 3, 3, 4, 5, 6, 7 };
int is_sorted()
{
int i, sorted = 1;
/*判定数组是否是有序的*/
for (i = 1; i < LEN; i++)
sorted = sorted && a[i-1] <= a[i];
return sorted;
}
int mustbe(int start, int end, int number)
{
int i;
for (i = 0; i < LEN; i++) {
/*确定数组合法，并且起始标志正确*/
if (i >= start && i <= end) {
continue;
/*确定该数字存在于数组中*/
if (a[i] == number) {
return 0;
}else {
printf("要查找的数字不再数组中！");
}
}
}
return 1;
}
int binarysearch(int number)
{
/*对起始点中点和终点进行标记*/
int mid = 0;
int start = 0;
int end = LEN - 1;
/*数组校验*/
assert(is_sorted());
while (start <= end) {
/*起始终点标志校验以及要查找的数字存在校验*/
assert(mustbe(start, end, number));
/*中点选择*/
mid = (start + end) / 2;
if (a[mid] < number) {
start = mid + 1;
}else if (a[mid] > number) {
end = mid - 1;
}else {
return mid;
}
}
/*起始终点标志校验以及要查找的数字存在校验*/
assert(mustbe(start, end, number));
return -1;
}
int main(void)
{
int i_number = 0;
printf("请输入您要查找的数字:");
scanf("%d", &i_number);
printf("您要查找的数字%d在数组中!\n", binarysearch(i_number));
return 0;
}
此程序已经在unix环境下用vi调试通过了,在windows环境下用VC6.0调试通过。
一维数组(折半的前提是数组元素已经有序排列)可以自己更改！
热心网友
时间：2023-10-30 08:38
------------------------------------------------------------
int binarySearch(int list[],int key,int arraySize){
int low = 0;
int high = arraySize - 1;
while(high >= low)
{
int mid = (low+high)/2;
if(key < list[mid]) high = mid - 1;
else if (key == list[mid]) return mid;
else low = mid + 1;
}
return -low - 1;
}
热心网友
时间：2023-10-30 08:39
var
a:array[1..maxnum] of integer;
N_find,i,j,mid:integer;
judge:boolean;
begin
readln(N_find);
i:=1;
j:=n;
judge:=false;
while not judge do
begin
mid:=(i+j) div 2;
if a[mid]=N_find then
begin
writeln('location: ',mid,);
judge:=true;
end;
if N_found>a[mid]
then i:=mid+1
else j:=mid-1;
end;
if not judge then writeln('NO data');
end.
热心网友
时间：2023-10-30 08:39
悬赏分：200 - 离问题结束还有 19 天 22 小时
编程实现在一维数组中的折半查找算法
