understanding searching and sorting

This is a discussion on understanding searching and sorting within the C++ Programming forums, part of the General Programming Boards category; In the function definition of a binary search algorithm, what's the purpose of first <= last in this line of ...

  1. #1
    Un Artiste Extraordinaire volk's Avatar
    Join Date
    Dec 2002
    Posts
    357

    understanding searching and sorting

    In the function definition of a binary search algorithm, what's the purpose of first <= last in this line of code?
    Code:
    while (!found && first <= last)
    Also, why does one have to be subtracted from the number of elements in the for loop in a linear search algorithm?
    Code:
    for (int i = 0; i < number_of_elements - 1; i++)

  2. #2
    Registered User
    Join Date
    Feb 2003
    Posts
    162
    1st) If First (which is changed everytime time you go throught the search), is larger than the last element of the array, then obviously the key doesn't exist in there...If the first is smaller than the last, then there is still a possibility that the key your looking for is somewhere there, so thats why it has that condition

    2nd) i think that tidbit of code is wrong....I haven't used the linear search in a while, but if I remember correctly it's either i < number_elements, or i <= number_elements .....

  3. #3
    Un Artiste Extraordinaire volk's Avatar
    Join Date
    Dec 2002
    Posts
    357
    I meant bubble sort instead of linear search.

  4. #4
    Registered User
    Join Date
    Feb 2003
    Posts
    162
    with the bubble sort, the last 2 items in the array are swapped, so the 2nd to last, and last are swapped, and if you had the for loop setup with the last, and not hte last - 1, it would swap the last with the last + 1, which is obviously non existent causing some serious problems.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. *Help*in sorting and searching algorithm
    By yuentong in forum C++ Programming
    Replies: 1
    Last Post: 03-07-2009, 10:43 AM
  2. Doxygen failing
    By Elysia in forum A Brief History of Cprogramming.com
    Replies: 19
    Last Post: 04-16-2008, 02:24 PM
  3. Help with sorting a text file database
    By bds824 in forum C Programming
    Replies: 5
    Last Post: 02-14-2006, 11:58 PM
  4. sorting and searching
    By rattex33 in forum C Programming
    Replies: 2
    Last Post: 10-23-2002, 05:11 AM
  5. problem in sorting and searching
    By ygfperson in forum C++ Programming
    Replies: 3
    Last Post: 04-16-2002, 08:47 PM

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