Answered by:
question about searching in list

Hi ,
I have a list of lacs of records like 316798111156211289... 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??
Question
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!
 Proposed as answer by Vidya Bhatt Friday, February 24, 2012 8:33 AM
 Unproposed as answer by Carl DanielModerator Sunday, February 26, 2012 6:24 AM
 Marked as answer by Carl DanielModerator Monday, February 27, 2012 2:57 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 nonnegative 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!
 Edited by Carl DanielModerator Thursday, February 23, 2012 3:50 PM
 Marked as answer by Carl DanielModerator Monday, February 27, 2012 2:57 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 Edited by Marco MinervaMVP Thursday, February 23, 2012 2:08 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 Edited by Marco MinervaMVP Thursday, February 23, 2012 2:21 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 
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 nonnegative 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!
 Edited by Carl DanielModerator Thursday, February 23, 2012 3:50 PM
 Marked as answer by Carl DanielModerator Monday, February 27, 2012 2:57 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!
 Proposed as answer by Vidya Bhatt Friday, February 24, 2012 8:33 AM
 Unproposed as answer by Carl DanielModerator Sunday, February 26, 2012 6:24 AM
 Marked as answer by Carl DanielModerator Monday, February 27, 2012 2:57 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!
 Edited by Carl DanielModerator Sunday, February 26, 2012 6:25 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!

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!