Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Recursive BInary Search on a DoublyLinkedList
New Posts  All Forums:Forum Nav:

Recursive BInary Search on a DoublyLinkedList

post #1 of 7
Thread Starter 
Hey there so im having to do exactly what the title says. My program reads in a list of ints sorts them then needs to sort them so from main i basically have
list.add(-999);
list.add(4);
list.add(-54);
etc etc its 22 ints long they get sorted then i need to search the list specifically like the title says. I have it mostly working, the search finds the entries if they are on the ends of the list like -999 i can not seem to find out what is wrong. This is an assignment and i do not want an answer but i do want help i can not find my error. I will attach the code in a .txt as well as the input files used incase you like this and want to work on it lol
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
post #2 of 7
Correct me if I'm wrong, but any LinkedList (the doublyLinkedList too, for that matter) is a non-indexed collection, therefore any kind of binary search is impossible?
My Rig
(14 items)
 
Ex-wife's Rig
(15 items)
 
 
CPUMotherboardGraphicsRAM
Core i5 4460 AsRock H81M-DG4 Sapphire Rx470 Platinum KVR 1600 16Gb 
Hard DriveHard DriveCoolingOS
2x Seagate 3Tb Samsung 850 EVO 120 Scythe Ninja 3 Rev.B Windows 10 Pro 
MonitorKeyboardPowerCase
Fujitsu Siemens A17-2A Logitech K280e SuperFlower SF-550K12XP Thermaltake Versa H25 
MouseAudio
Logitech G402 Sony MDR XD150 
CPUMotherboardGraphicsRAM
Athlon 750K 4.0Ghz AsRock FM2A75 Pro4+ Sapphire R9 270X Dual-X Kingston 2x4Gb 1600 
Hard DriveHard DriveOptical DriveCooling
Samsung 850 EVO 120  Western Digital 320Gb LiteON DVD-RW CoolerMaster Hyper Z600 
OSMonitorKeyboardPower
Windows 7 Pro x64 Toshiba 32" FullHD TV Logitech FSP Hexa 550 
CaseMouse
DeLUX Logitech 
  hide details  
Reply
My Rig
(14 items)
 
Ex-wife's Rig
(15 items)
 
 
CPUMotherboardGraphicsRAM
Core i5 4460 AsRock H81M-DG4 Sapphire Rx470 Platinum KVR 1600 16Gb 
Hard DriveHard DriveCoolingOS
2x Seagate 3Tb Samsung 850 EVO 120 Scythe Ninja 3 Rev.B Windows 10 Pro 
MonitorKeyboardPowerCase
Fujitsu Siemens A17-2A Logitech K280e SuperFlower SF-550K12XP Thermaltake Versa H25 
MouseAudio
Logitech G402 Sony MDR XD150 
CPUMotherboardGraphicsRAM
Athlon 750K 4.0Ghz AsRock FM2A75 Pro4+ Sapphire R9 270X Dual-X Kingston 2x4Gb 1600 
Hard DriveHard DriveOptical DriveCooling
Samsung 850 EVO 120  Western Digital 320Gb LiteON DVD-RW CoolerMaster Hyper Z600 
OSMonitorKeyboardPower
Windows 7 Pro x64 Toshiba 32" FullHD TV Logitech FSP Hexa 550 
CaseMouse
DeLUX Logitech 
  hide details  
Reply
post #3 of 7
The max amount of searches for a list of 22 ints is going to be 5...using binary search. Once you have your list sorted...you need to make the recursion search method...and inside that method it basically calls itself repeatedly until the "key" is found...if the "key" is not found within 5 searches...then the key is not in the list.

*It would be much, much easier to copy your sorted list to an array before doing the search, but you can still do the recursive search with just the list...but it would be more difficult to implement and more innefficient.
Edited by surfbumb - 6/2/11 at 11:02am
Black Silence
(15 items)
 
  
CPUMotherboardRAMHard Drive
i5 3570k @ 4.5 GHz Asus P8Z77-M Pro Kingston HyperX Genesis 8 GB - 1600 MHz Seagate Barracuda 250 GB 
Optical DriveCoolingOSMonitor
Samsung WriteMaster Noctua NH-D14 Windows 10 ASUS VS24AH-P 
KeyboardPowerCaseMouse
Logitech Navigator Enermax Infiniti 650W Fractal R3 Black Pearl Razer Death Adder 
Mouse PadAudio
SteelSeries QcK Mass Altec Lansing FX4021 
  hide details  
Reply
Black Silence
(15 items)
 
  
CPUMotherboardRAMHard Drive
i5 3570k @ 4.5 GHz Asus P8Z77-M Pro Kingston HyperX Genesis 8 GB - 1600 MHz Seagate Barracuda 250 GB 
Optical DriveCoolingOSMonitor
Samsung WriteMaster Noctua NH-D14 Windows 10 ASUS VS24AH-P 
KeyboardPowerCaseMouse
Logitech Navigator Enermax Infiniti 650W Fractal R3 Black Pearl Razer Death Adder 
Mouse PadAudio
SteelSeries QcK Mass Altec Lansing FX4021 
  hide details  
Reply
post #4 of 7
Thread Starter 
This is the description:
"In this question, you will take an ordered doubly-linked list and perform a recursive binary search on it. Your program should read in a list of integers as in question 1, sort it, then read in another file containing integers that will be used as search keys for the binary search. (if you could not the first question working, simply read in an ordered list). Each search should either return the node with the corresponding key, or null if no such node exists. You need not worry about returning multiple nodes with the same key, simply return one of them.

You can do the binary search in one of two ways: either you can split the linked list in half with each subsequent binary search call, thus reducing the list until either the element is found, or there is only one element left. Alternatively, you can just use Node pointers without needing to copy, split, or modify the list in any way. "

We are not allowed to copy it into an array that would be easy it must be done on the linked list as it not impossible i have it almost working but i need help with my recursive calls
im attaching my updated code and it looks like it should work but i can not find the bug.
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
post #5 of 7
Code:
//resursive binary search method


public int recursiveBinarySearch(int[] list, int low, int high, int key){

      private int mid;

      mid = (low + high)/2;
  
      if(list[mid] > key)
              return recursiveBinarySearch(list, low, mid - 1, key);
      else if(list[mid] < key)
              return recursiveBinarySearch(list, mid + 1, high, key);
      else return mid;

}
you can use a counter variable to determine if the key is not in the list...pretty simple there.
Black Silence
(15 items)
 
  
CPUMotherboardRAMHard Drive
i5 3570k @ 4.5 GHz Asus P8Z77-M Pro Kingston HyperX Genesis 8 GB - 1600 MHz Seagate Barracuda 250 GB 
Optical DriveCoolingOSMonitor
Samsung WriteMaster Noctua NH-D14 Windows 10 ASUS VS24AH-P 
KeyboardPowerCaseMouse
Logitech Navigator Enermax Infiniti 650W Fractal R3 Black Pearl Razer Death Adder 
Mouse PadAudio
SteelSeries QcK Mass Altec Lansing FX4021 
  hide details  
Reply
Black Silence
(15 items)
 
  
CPUMotherboardRAMHard Drive
i5 3570k @ 4.5 GHz Asus P8Z77-M Pro Kingston HyperX Genesis 8 GB - 1600 MHz Seagate Barracuda 250 GB 
Optical DriveCoolingOSMonitor
Samsung WriteMaster Noctua NH-D14 Windows 10 ASUS VS24AH-P 
KeyboardPowerCaseMouse
Logitech Navigator Enermax Infiniti 650W Fractal R3 Black Pearl Razer Death Adder 
Mouse PadAudio
SteelSeries QcK Mass Altec Lansing FX4021 
  hide details  
Reply
post #6 of 7
Thread Starter 
i have no counter as it is a linked list basically what im trying to do it cut the list in half based on which side key is to be on but im also removing the mid and end points so that they are not searched again via mid.getNext() and end.getPrev() etc. and i guess my sudo counter is middle which is the middle of the list as o keep track of the list size so it is passed down each time but somewhere in there it is not responding correctly
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
post #7 of 7
Quote:
Originally Posted by Sin Cities Sin View Post
i have no counter as it is a linked list basically what im trying to do it cut the list in half based on which side key is to be on but im also removing the mid and end points so that they are not searched again via mid.getNext() and end.getPrev() etc. and i guess my sudo counter is middle which is the middle of the list as o keep track of the list size so it is passed down each time but somewhere in there it is not responding correctly
yeah, i didnt see that you couldn't use an array...that would make it too easy i guess. How did my sort algorithm work from the other day?

If I were you I would keep at it...it seems you have the right logic. What I would do is...create a new list everytime the search fails...and put the new list as one of the parameters in the recursive call. The list will shrink by half everytime as you know each time there is a recursive call.

Code:
//lets say i have these numbers and my key is 8...10 is the mid

2 4 6 8 10 12 14 16 18 20

//the node that contains 8...set the next node to null...now the list is cut in half...return that list

//if your key is 12...have list point to the node that contains 12...return that list....see how easy that was.

Edited by surfbumb - 6/2/11 at 6:20pm
Black Silence
(15 items)
 
  
CPUMotherboardRAMHard Drive
i5 3570k @ 4.5 GHz Asus P8Z77-M Pro Kingston HyperX Genesis 8 GB - 1600 MHz Seagate Barracuda 250 GB 
Optical DriveCoolingOSMonitor
Samsung WriteMaster Noctua NH-D14 Windows 10 ASUS VS24AH-P 
KeyboardPowerCaseMouse
Logitech Navigator Enermax Infiniti 650W Fractal R3 Black Pearl Razer Death Adder 
Mouse PadAudio
SteelSeries QcK Mass Altec Lansing FX4021 
  hide details  
Reply
Black Silence
(15 items)
 
  
CPUMotherboardRAMHard Drive
i5 3570k @ 4.5 GHz Asus P8Z77-M Pro Kingston HyperX Genesis 8 GB - 1600 MHz Seagate Barracuda 250 GB 
Optical DriveCoolingOSMonitor
Samsung WriteMaster Noctua NH-D14 Windows 10 ASUS VS24AH-P 
KeyboardPowerCaseMouse
Logitech Navigator Enermax Infiniti 650W Fractal R3 Black Pearl Razer Death Adder 
Mouse PadAudio
SteelSeries QcK Mass Altec Lansing FX4021 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Recursive BInary Search on a DoublyLinkedList