help with binary search

This is a discussion on help with binary search within the C Programming forums, part of the General Programming Boards category; ok i sorted an array of structures and now i need help placing them in boxes so that the number ...

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    19

    help with binary search

    ok i sorted an array of structures and now i need help placing them in boxes
    so that the number of boxes required is optimal


    i have an idea of what i could do

    - find the biggest item possible, and switch it with the first element of the array
    -decrease my box' size by the item chosen and search another item
    -With the new item, you switch it with the 2nd element of the array
    -You repeat it until all the items have been switched

    here is my code so far that sorts my array...i just dont know how to use the binary search
    i attached the input file im using


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    typedef struct {
        int size;
        char name[21];
        int boxnumber;
        int used;
    }item;
    
    void swap(item *a, item *b){
        item tmp;
        tmp = *a;
        *a = *b;
        *b = tmp;
    }
    
    void bubbleSort(item a[], int size){
        int i, j;
    
        for (i=0; i<size-1; i++){
            for (j=size-1; j>i; j--)
                if (a[j].size > a[j-1].size)
                    swap(&a[j], &a[j-1]);
        }
    }
    
    int bfind(item a[],int val,  int size){
      int left = 0;
      int right = size;
      int middle;
    
      do {
        middle = (left + right) / 2;
    
        if(a[middle].size < val)
          left = middle + 1;
        else if(a[middle].size > val)
          right = middle - 1;
        else
          return middle;
      } while(left <= right);
    
    
        return middle-1;
    }
    
    int main(void) {
        int s,n;
        int i;
        int newboxsize;
        item *array;
    
        FILE *iFile;
        iFile = fopen ("inputzou.txt","r");
    
        fscanf (iFile, "%d, %d", &s, &n);
    
        printf (" \n");
    
        array = calloc (n, sizeof(item));
    
        for (i=0;i<n;i++){
            array[i].boxnumber=0;
            array[i].used=0;
    
    			fscanf(iFile, "%s %d", array[i].name, &array[i].size);
        }
    
        bubbleSort(array, n);
    
    
    
        free(array);
    
        fclose(iFile);
    
        return 0;
    }
    Attached Files Attached Files
    Last edited by sass208; 11-26-2006 at 12:29 PM.

  2. #2
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Ummm...what exactly is it you're trying to do ?
    Is it 0-1 knapsack or are you actually trying to search an array with binary search ? It's not quite clear what the question is...
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  3. #3
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,682
    So what is the actual problem with the code

    ssharish2005

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  2. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 06:19 AM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21