Question

C语言中怎么用折半查找法查找字符

Answer 1

折半查找要求元素集合必须是有序的，如果是无序的，那就没办法了。预先排序的话，效率还要低些，除非要查找很多元素。如果是有序的，那就用下面这个方法吧。

int binary(char* array, int n, char key) {
int left = -1;
int right = n;
while (left + 1 != right) {
int i = (left + right) / 2;
if (key == array[i]) return i;
if (key < array[i]) right = i;
else left = i;
}
return -1;
}

Answer 2

前提是有序 序列。排序是比较的字符的ASCII码
先排序在查找

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 10

void bubble(char str[])
{
int i,j;
char t;
for(i=0;i<strlen(str)-1;i++)
{
for(j=0;j<strlen(str)-i-1;j++)
if(str[j]>str[j+1])
{
t=str[j];
str[j]=str[j+1];
str[j+1]=t;
}
}
}
void select(char str[],char c)
{
int l=0,h=strlen(str),i;
while(l<=h)
{
i=(l+h)/2;
if(str[i]==c)
{
printf("The character is the %dth in the array.",i+1);
return;
}
else if (str[i]>c)h=i-1;
else l=i+1;
}
printf("The character cannot be found.");
}

int main(void)
{
int i;
char str[]="streetsovc";
char c='r'; //要查找对象
printf("%d",strlen(str));
bubble(str);
printf("拍序后\n");
printf("%s\n",str);
select(str,c);
system("pause");
return(0);
}

Answer 3

折半查找：
#include <stdio.h>
#define N 10
int binary_search(int a[], int key, int left, int right);
void bubble_sort(int a[]);
int main(void)
{
int i, key, a[] = {74, 5, 45, 2, 21, 6, 7, 8, 15, 10};
printf("Enter search number:\n");
scanf("%d", &key);
bubble_sort(a);
i = binary_search(a, key, 0, N - 1);
printf("i = %d\n", i);
return 0;
}
int binary_search(int a[], int key, int left, int right)
{
int mid;
mid = (left + right) / 2;
if (left > right)
return -1;
else if (left <= right)
{
if (a[mid] == key)
return mid;
else if (a[mid] > key)
binary_search(a, key, left, mid - 1);
else if (a[mid] < key)
binary_search(a, key, mid + 1, right);
}
}
void bubble_sort(int a[])
{
int i, j, temp;
for (i = 0; i < N - 1; i++)
for ( j = 0; j < N - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}

这是我在网上找的一个例子，你可以参考一下