binary search

[chauncey005]

Does anyone know how I could search a 2D array using binary search and if so explain each part of the code for me? I would appreciate it very much. Thank you!

[Thantos]

It depends on how the data is being sorted in the array. Might be helpful to show the code the fills the array.

[Codeplug]

search: binary search

gg

[WaltP]

What is the order of the array's contents? Binary sorts are only good with sorted lists AFAI Remember

[Thantos]

You are correct WaltP. Binary search is useless in an unsorted array. Heck I'd venture to guess that any searching method, besides stepping through each item one by one, would not work on an unsorted array.

[chauncey005]

Sorry about that guys. It feels the array with random characters that are already sorted alphabetically be the first character.

char *RandomString(int length){

  int i, size;
  char *string;

  size = 1 + rand() % length;

  string = calloc(size + 1, sizeof(char));

  for(i = 0; i < size; i++){
    string[i] = (char)((rand() % 26) + 65);
  }
  string[i] = '\0';

  return string;

}

[chauncey005]

It is still pretty early for me, I apologize about the english. What I meant to say is that the code fills the array with random capital letters that are already sorted alphabetically by the first character and length.

[Prelude]

A multidimensional array when passed to a function is simply a pointer to the first element. Because multidimensional arrays are actually stored in memory as a large single dimensional array, you can treat them exactly the same in your search routine as long as you get the sizes right.

Warning: An example follows

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

int cmp ( const void *a, const void *b )
{
  int aa = *(int*)a;
  int bb = *(int*)b;

  if ( aa < bb )
    return -1;
  else if ( aa > bb )
    return +1;
  else
    return 0;
}

int main( void )
{
  int values[][4] = { 
    { 1, 2, 3, 4 },
    { 5, 6, 7, 8 },
  };
  int *found;
  int key = 7;

  found = bsearch ( &key, values, 8, sizeof ( int ), cmp );
  if ( found != NULL )
    printf ( "%d is in the array\n", *found );
  else
    printf ( "%d is not in the array\n", key );

  return 0;
}

[WaltP]

Originally posted by chauncey005 on 12-03-2003
Does anyone know how I could search a 2D array using binary search and if so explain each part of the code for me? I would appreciate it very much. Thank you!

Originally posted by chauncey005 on 12-04-2003
Sorry about that guys. It feels the array with random characters that are already sorted alphabetically be the first character.

char *RandomString(int length){

  int i, size;
  char *string;

  size = 1 + rand() % length;

  string = calloc(size + 1, sizeof(char));

  for(i = 0; i < size; i++){
    string[i] = (char)((rand() % 26) + 65);
  }
  string[i] = '\0';

  return string;

}

Originally you mention 2D which is a matrix, i.e buffer[x][y]. Then you show code that loads a 1D array, i.e buffer[x]. So which is it? If it's 2D, it depends on how the buffer is loaded (row first or column first). 1D doesn't matter, if it's sorted, it's obvious.

[chauncey005]

My apologies Walt, its a 1D array. What I was meaning to say is that I have an array of the number of random strings assigned and inside the indexes actually list the random strings themselves. I hope I have made it a little more clear. Thanks again!

[WaltP]

Originally posted by chauncey005
My apologies Walt, its a 1D array. What I was meaning to say is that I have an array of the number of random strings assigned and inside the indexes actually list the random strings themselves. I hope I have made it a little more clear. Thanks again!

In that case, it's simple. Assume there are n entries in the list.

first = 0
last = n-1
num = n/2

loop
{
    test array[first + num)]
    if array[t] < target last = num
    if array[t] > target first = num
    num = num/2
}

Something like that wil be close.