none
question about searching in list

    Question

  • Hi ,

    I have a list of lacs of records like 31-67-98-111-156-211-289-... which is in ascending order and I want to search number 81 in that list, so I want a number which is just greater than my search number i.e.81 and here it is 98 which is expected..and after getting 98 I will search my number in previous record i.e.in 67..I just want a number which is first greater than my search key value..So how to achieve this search??

    Thursday, February 23, 2012 1:58 PM

Answers

  • Hi Shailesh, I have written the below function which will give you the first greater number (on not found) OR the same number (if the match found).

    private int SearchNumber(int low, int high, List<int> numbers, int searchNumber)
    {
        if (low == high)
        {
            return numbers[low];
        }
    
        if (numbers[low + (high - low) / 2] >= searchNumber)
        {
            high = low + (high - low) / 2 ;
        }
        else
        {
            low = low + (high - low) / 2 + 1;
        }
    
        return SearchNumber(low, high, numbers, searchNumber);
    }

    You can call this function as below,

    List<int> numbers = new List<int>() { 1, 5, 10, 12, 13, 18, 21, 23, 26, 31, 39, 40, 44 };
    int match = SearchNumber(0, numbers.Count - 1, numbers, 41);
    MessageBox.Show(match.ToString());

    I hope this helps.


    Please mark this post as answer if it solved your problem. Happy Programming!

    Thursday, February 23, 2012 4:38 PM
  • It is very time consuming to search linear in lacs of records...I want optimized i.e. fast algorithm. Binary search is for perfect search hence I cant use it..??

    Two points.  First, it's not very slow.  Unless your list has millions of items, the difference is barely measurable and rarely enough to make a significant difference in the performance of the overall application.

    Second, if you want a binary search then use one.  System.Collections.Generic.List<T>.BinarySearch has been in the framework since .NET 2.0.  Note the return value from BinarySearch if the item is not found:  it's the 1's complement of the index where the item would be if it were present.  So, you have two cases to handle:

    1. BinarySearch returns a non-negative value.  In this case, the number you searched for is in the list, and the returned value is the index.

    2. BinarySearch returns a negative value.  In this case, the first number in your list that's higher than what you searched for is in the list at the index that's the 1's complement of the return value.  In C# the 1's complement operator is spelled ~.

    int result = myList.BinarySearch(desiredNumber);
    if (result < 0)
       return myList[~result];
    else
       return myList[result];


    -cd Mark the best replies as answers!




    Thursday, February 23, 2012 3:44 PM

All replies

  • If you have your records in a array or a List of int, you can easily use LINQ:

    var records = new List<int> { 31, 67, 98, 111, 156, 211, 289 };
    int keyValue = 81;
    var number = (from r in records where r > keyValue select r).FirstOrDefault();  // Returns 98.</int>


    Marco Minerva [MCPD]
    Blog: http://blogs.ugidotnet.org/marcom
    Twitter: @marcominerva

    Thursday, February 23, 2012 2:08 PM
  • I am using framework 2.0..Is there any another way??
    Thursday, February 23, 2012 2:11 PM
  • The simplest way is a for cycle:

    int number;
    foreach (var n in records)
    {
        if (n > keyValue)
        {
            number = n;
            break;
        }
    }


    Marco Minerva [MCPD]
    Blog: http://blogs.ugidotnet.org/marcom
    Twitter: @marcominerva

    Thursday, February 23, 2012 2:20 PM
  • It is very time consuming to search linear in lacs of records...I want optimized i.e. fast algorithm. Binary search is for perfect search hence I cant use it..??
    Thursday, February 23, 2012 2:43 PM
  • Isn't so simple, because you need to know if the midpoint value that you are analyzing in binary search is really the first one grater than your value.

    Marco Minerva [MCPD]
    Blog: http://blogs.ugidotnet.org/marcom
    Twitter: @marcominerva

    Thursday, February 23, 2012 3:08 PM
  • It is very time consuming to search linear in lacs of records...I want optimized i.e. fast algorithm. Binary search is for perfect search hence I cant use it..??

    Two points.  First, it's not very slow.  Unless your list has millions of items, the difference is barely measurable and rarely enough to make a significant difference in the performance of the overall application.

    Second, if you want a binary search then use one.  System.Collections.Generic.List<T>.BinarySearch has been in the framework since .NET 2.0.  Note the return value from BinarySearch if the item is not found:  it's the 1's complement of the index where the item would be if it were present.  So, you have two cases to handle:

    1. BinarySearch returns a non-negative value.  In this case, the number you searched for is in the list, and the returned value is the index.

    2. BinarySearch returns a negative value.  In this case, the first number in your list that's higher than what you searched for is in the list at the index that's the 1's complement of the return value.  In C# the 1's complement operator is spelled ~.

    int result = myList.BinarySearch(desiredNumber);
    if (result < 0)
       return myList[~result];
    else
       return myList[result];


    -cd Mark the best replies as answers!




    Thursday, February 23, 2012 3:44 PM
  • Hi Shailesh, I have written the below function which will give you the first greater number (on not found) OR the same number (if the match found).

    private int SearchNumber(int low, int high, List<int> numbers, int searchNumber)
    {
        if (low == high)
        {
            return numbers[low];
        }
    
        if (numbers[low + (high - low) / 2] >= searchNumber)
        {
            high = low + (high - low) / 2 ;
        }
        else
        {
            low = low + (high - low) / 2 + 1;
        }
    
        return SearchNumber(low, high, numbers, searchNumber);
    }

    You can call this function as below,

    List<int> numbers = new List<int>() { 1, 5, 10, 12, 13, 18, 21, 23, 26, 31, 39, 40, 44 };
    int match = SearchNumber(0, numbers.Count - 1, numbers, 41);
    MessageBox.Show(match.ToString());

    I hope this helps.


    Please mark this post as answer if it solved your problem. Happy Programming!

    Thursday, February 23, 2012 4:38 PM
  • Hi Shailesh, I have written the below function which will give you the first greater number (on not found) OR the same number (if the match found).


    This function has a bounds error in it.  Think about what happens if you pass in a number greater than the largest in the list?  With this API, what should the function return in such a case?

    (btw, the snippet I posted above using List<T>.BinarySearch has the same problem, but it wasn't my intent to write a complete function, just to illuminate the existence of BinarySearch).


    -cd Mark the best replies as answers!


    Sunday, February 26, 2012 6:24 AM
  • This function has a bounds error in it.  Think about what happens if you pass in a number greater than the largest in the list?  With this API, what should the function return in such a case?

    When the number is greater than largest in the list - But this was also not there in the requirement  :)

    Anyways, he has already marked my solution as answer here to the same question. So, looks he is satisfied with the solution. 


    Please mark this post as answer if it solved your problem. Happy Programming!

    Sunday, February 26, 2012 7:02 AM
  • This function has a bounds error in it.  Think about what happens if you pass in a number greater than the largest in the list?  With this API, what should the function return in such a case?

    When the number is greater than largest in the list - But this was also not there in the requirement  :)

    Anyways, he has already marked my solution as answer here to the same question. So, looks he is satisfied with the solution. 


    Please mark this post as answer if it solved your problem. Happy Programming!

    Well, he'll figure it out when his program crashes with an index out of bounds exception.

    I hate it when people post duplicate threads - If I'd seen the other before this one had some much action, I would have deleted one of them.  As is, I'm going to go ahead and mark what are effectively the same posts as answers in this version as well, in case someone searching for an answer finds this thread and not the other one.


    -cd Mark the best replies as answers!

    Monday, February 27, 2012 2:56 PM