CODEWITHSUNDEEP
cstringbinary-search
user3699735
user3699735

Reputation: 21

Having trouble with my binary search in C

I am having trouble with a binary search on strings in c. I use the strcmp function to compare the strings, but I still get no output when I type in a name that I know is in the list.

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_STRING_LEN 25

void insert_sata(char **strings, const char* filename, int size);
void allocate( char ***strings, int size);
int binary_search(char **strings, char *target, int start_idx, int end_idx);

int main(int argc, char* argv[]){

    if(argc != 4){
        printf("Wrong number of args");
    }

    char **pointer;
    int size = atoi(argv[1]);


    allocate(&pointer, size);
    insert_data(pointer, argv[2], size);

    int x;
    int z = 1;
    char search_name[MAX_STRING_LEN];

    while( z == 1){
        printf("\nEnter a name to search for: ");
        scanf("%s", search_name);
        x = binary_search(pointer, search_name, 0, size);
        printf("\nContinue searching names? ( 1 = yes, 0 = No):");
        scanf("%d", &z);
    }
}



void allocate(char ***strings, int size){

    int i;
    *strings =  malloc(sizeof(**strings) * size);
    for( i = 0; i < size; i++)
    {
        (*strings)[i] = malloc(sizeof(char) * MAX_STRING_LEN);
    }
}

void insert_data(char **strings, const char* filename, int size){

    FILE *input;
    input = fopen(filename, "r");

    int i;
    for (i = 0; i < size; i++){

        fscanf(input,"%24s", strings[i]);

    }

    fclose(input);
}

int binary_search(char **strings, char *target, int start_idx, int end_idx){

    int result;
    int mid_idx = 0;

    while( end_idx >= start_idx){
        mid_idx = (end_idx + start_idx) / 2;

        result = strcmp(strings[mid_idx], target);

        if(result > 0){
            end_idx = start_idx - 1;
        }
        else if (result < 0){
            start_idx = mid_idx + 1;
        }

        else if( result == 0){
            printf("%s was found in the set", target);

        }
    }
}

The binary search is the function that is giving me trouble. I do not recieve any seg faults or anything, just nothing is displayed when I search a name that is in the file. Here is the list of names that I scan into the program.

Upvotes: 0

Views: 110

Answers (3)

CiaPan
CiaPan

Reputation: 9571

Your input list isn't sorted and your program doesn't seem to try to sort it. Suppose you look for 'susan' - first comparision is 'susan' to 'aden', and the search area gets narrowed to last 5 items, while 'susan' is at the second position......

Upvotes: 3

king_nak
king_nak

Reputation: 11513

The binary search algorithm requires that the list is sorted. Your example list isn't, so the algorithm will not work

Upvotes: 0

Paul Roub
Paul Roub

Reputation: 36438

This: 

if (result > 0) {
   end_idx = start_idx - 1;
}

is probably mean to be:

if (result > 0) {
  end_idx = mid_idx - 1;
}

Upvotes: 0

Related Questions