finding the largest number in a binary search

This is a discussion on finding the largest number in a binary search within the C++ Programming forums, part of the General Programming Boards category; The 1st and foremost condition of Binary Search is that the array must be sorted. Binary search is used to ...

  1. #16
    Registered User
    Join Date
    Jan 2008
    Posts
    225
    The 1st and foremost condition of Binary Search is that the array must be sorted. Binary search is used to find a specific number, if you want to find the maximum number only then sort the array in descending order and print the value of 0th index.
    If you don't want the array to be sorted you should go for sequential search instead.

  2. #17
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    It is possible to attempt to perform a binary search on an array that might not be sorted, in a useful manner. I did this myself in my implenentation of an algorithm I called "Hopeful Search", listed on my webpage (See my sig). Basically you go about your way performing a recursive binary search as usual, then for any recursive call that fails to find the item, you do a recursive call on the other half anyway.

    1. If the array IS sorted and the item IS in the array then it takes O(log n) time.
    2. If the item is not in the array then it searches the whole array taking O(n) time.
    3. If the array is not sorted, then it takes O(n) time though it can often be quicker particularly if the array is partially sorted.

    This is of course much more useful if you know in advance that the item you are searching for is always in there.
    Nifty huh?!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #18
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Quote Originally Posted by iMalc View Post


    Nifty huh?!
    Not really, it's no better than a sequential search, which is way easier to program. Actually it's probably worse due to overhead in maintaining the "splits" of the binary search when the value doesn't fall into the half you are searching first.

  4. #19
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    It all depends on how likely the list is to be sorted. If it is sorted 90% of the time and the item is always present then of course it is going to be faster than a linear scan.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #20
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Quote Originally Posted by iMalc View Post
    It all depends on how likely the list is to be sorted. If it is sorted 90% of the time and the item is always present then of course it is going to be faster than a linear scan.
    I guess it's easy to make your algorithm optimal when you first set up all the confining conditions.

    My linear search routine is always faster when the item searched for is in the first few elements which is 90% of the time.


    Seriously, if you have a list that is sometimes sorted and sometimes not, it would probably just be easier to sort it the 10% of the time when it's not sorted than trying to do a pseudo binary sort on an unsorted list. And now since you are routinely keeping it sorted, it won't even be 10%

  6. #21
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    Sure, I agree. I'm not trying to twist any old problem into one that would specifically suit this particular algorithm as a solution though. I'm just saying that most unusual algorithms out there can be the optimal solution in some real-world scenario. I would never twist a problem to fit a specific solution. Nor would I make it out to be any more useful than it is, the algorithm is most of the time completely pointless, but it was relevant to the discussion.

    For example:
    A part of your program interoperates with a 3rd party library. That library may provides as output to some function, an array of items that is sorted using a sorting algorithm that has a tiny bug which of course you cannot fix as the company has gone bust or whatever. The bug is no more serious than causing a few items to occasionally be out of order though. You are not able to sort the array correctly before searching because the library also has pointers to some of the items and will fail if those items are moved, and because you only need to perform a small number of searches before a new array is returned anyway and sorting would add too much time. Thus you must treat it as read-only. You also happen to know that by the very nature of the particluar problem, that the item you are searching for is always in the array. The array is very large and you do not have time to spend searching through on average half the items each time as with a sequential search, however the occasional slow search here and there is okay since that slowdown is amortised out.

    Now I'm not saying that one would ever intentionally create such a scenario. I'm saying that if one were faced with such a scenario, it would be in your best interests to be able to adapt and come up with a creative solution which would quite possibly match the algorithm I described.
    Last edited by iMalc; 07-31-2008 at 03:23 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with binary search.
    By StateofMind in forum C Programming
    Replies: 6
    Last Post: 05-06-2009, 02:14 PM
  2. Issue w/ Guess My Number Program
    By mkylman in forum C++ Programming
    Replies: 5
    Last Post: 08-23-2007, 01:31 AM
  3. Replies: 3
    Last Post: 11-25-2006, 03:14 PM
  4. Replies: 9
    Last Post: 10-07-2006, 05:37 AM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM

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