2 Replies - 1384 Views - Last Post: 05 April 2007 - 08:54 AM Rate Topic: -----

#1 shezzy  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 194
  • Joined: 28-January 07

List binary search program

Posted 05 April 2007 - 08:20 AM




public class OrderedStringList {
	int max = 100;

	String strArray[] = new String[max];

	int count = 0;

	public static void main(String[] args) {
		
		OrderedStringList test = new OrderedStringList();

		// does nothing really with out driver class

	}

	public void add(String str) {
		if (count == 0) {
			strArray[0] = str;
			count++;
		} else {
			int result = binarySearch(str);
			if (result == -999) {
				String temp = strArray[0];
				strArray[0] = str;
				reorderArray(1, temp);
				count++;
			} else {
				System.out.println(result);
				if (result > 0) {
					String temp = strArray[result];
					strArray[result] = str;
					reorderArray(result + 1, temp);
					count++;
				} else {
					String temp = strArray[Math.abs(result)];
					strArray[Math.abs(result)] = str;
					reorderArray(Math.abs(result) + 1, temp);
					count++;

				}
			}
		}
	}

	public boolean remove(int badIndex) {
		if (badIndex < count - 1 && badIndex > 0) {
			for (int i = badIndex; i < count - 2; i++) // reorderes items in
			// array to keep in
			// order
			{
				strArray[i] = strArray[i + 1];
			}
			strArray[count - 1] = null;
			count--;
			return true; // returns true since operation sucessful

		} else {
			return false;// remove failed
		}
	}

	public void removeAll() {
		strArray = new String[max];
		count = 0;
	}

	public String returnStr(int index) {
		return strArray[index];
	}

	public int returnSize() {
		return count;
	}

	public int binarySearch(String searchItem) {
		int first = 0;
		int last = count - 1;
		int mid = 0;

		boolean found = false;

		// Loop until found or end of list.
		if (count == 0) {
			System.out.println("No items in list");
			return -1;
		} else {
			while (first <= last && !found) {
				// Find the middle.
				mid = (first + last) / 2;

				// Compare the middle item to the search item.
				if (strArray[mid].compareTo(searchItem) == 0)
					found = true;
				else { // Not found, readjust search parameters, halving the
					// size &
					// start over.
					if (strArray[mid].compareTo(searchItem) > 0) {

						last = mid - 1;
					} else {
						first = mid + 1;

					}
				}
			}

			if (found)
				return mid;
			else {
				if (mid == 0) {
					return -999; // value isnt in array but should be
						// inserted to index 0
				} else {
					return mid * -1;
				}
			}
		}
	}

	public String toString() {
		if (count == 0) {
			return "No items in list";
		} else {
			String response = "";
			for (int i = 0; i <= count - 1; i++) {
				response = response + " " + strArray[i];
			}
			return response;
		}
	}

	private void reorderArray(int begin, String newStr) {
		for (int i = begin; i < count; i++) {
			strArray[i] = newStr;
			newStr = strArray[i + 1];

		}
		strArray[count] = newStr;

	}

}











import java.io.*;

public class Driver {

	OrderedStringList runner = new OrderedStringList();

	public static void main(String[] args) throws IOException {
		Driver test = new Driver();
		test.menuPrompt();

	}

	public void menuPrompt() throws IOException {
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		int response = 100; // just a dummy initial value
		while (response != 898) {

			System.out.println("Please input a number for the following options");
			System.out.println("Press 1 to insert item to list");
			System.out.println("Press 2 to delete a item from list");
			System.out.println("Press 3 to get item from list");
							  System.out.println("Press 4 to search for a specified item in the list.");
			System.out.println("Press 5 to clear list");
			System.out.println("Press 6 to print size and content of list");
			System.out.println("Press 7 to exit program");
			System.out.println("Please input your selection: ");
			String answer = stdin.readLine();
			response = Integer.parseInt(answer);
			switch (response) {
			case 1:
				System.out.println("Selection 1 was made.");
				System.out.println("Enter item : ");
				String tName = stdin.readLine();

				runner.add(tName);
				// System.out.println("Item: "+tName+" inserted in position"+
				// inputIndex+" in the list");
				break;

			case 2:
				System.out.println("Selection 2 was made.");
				System.out.println("Index of item to be deleted: ");
				String t2Index = stdin.readLine();
				int input2Index = Integer.parseInt(t2Index);

				boolean result = runner.remove(input2Index);
				if (result == true) {
					System.out.println("Remove was successful");
				} else {
					System.out.println("Remove was unsuccessful");
				}
				break;
			case 3:
				System.out.println("Selection 3 was made");
			System.out.println("Please insert a index for item, assume index starts at 0: ");
				String t3Index = stdin.readLine();
				int input3Index = Integer.parseInt(t3Index);
				if (runner.returnStr(input3Index) != null) {
					System.out.println(runner.returnStr(input3Index));
				} else {
					System.out.println("invalid item at specified index");
				}

				break;
			case 4:

				System.out.println("Selection 4 was made.");
				System.out.println("Enter item to search for: ");
				String searchResponse = stdin.readLine();
				int ii = runner.binarySearch(searchResponse);
		if (ii == -999) { //-999 is dummy value so i know it belongs in0 but isnt there yet
					System.out.println("Item belongs at beginning of list");
				} else {
					if (ii > 0) {
			System.out.println(searchResponse+ " was found at index: " + ii);
					} else {
			System.out.println(searchResponse+ " belongs in index: " + Math.abs(ii));
					}
				}

				break;
			case 5:
				runner.removeAll();
				System.out.println("Selection 5 was made.");

				break;
			case 6:
				System.out.println("List contains :" + runner.returnSize()
						+ " strings");
				System.out.println(runner.toString());
				break;
			case 7:
				System.out.println("Selection 7 was made, GOODBYE!!");
				System.exit(1);
				break;

			}
		}
	}

}







sorry for the long post of code but i figured be the only way any one could help me by showing what im trying to do. This implemention uses a string array base and attempts a binary search by comparing two strings. This program also attempts to add the items in ascending order in lexographic terms as needed by binary searching. The possible return values are as follows for binary search,

if the response is = to a positive int then that means it is allready in the array and is located at that position. if it returns a negative value it means that the item is not in the array but should be inserted in the index when taking the absolute value of the returned index from binary search. the last return value can be -999 which means the item belongs at 0 index but is not currently in the array.

im having multiple problems.. for one it doesnt seem that my program is adding the strings to the array in the correct order, also my shifting seems to be off as even my tostring method shows null entries in the array. few other problems that when i remember ill post back =P any help would be appreciated

ill post back after school ;)

Is This A Good Question/Topic? 0
  • +

Replies To: List binary search program

#2 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: List binary search program

Posted 05 April 2007 - 08:45 AM

your add method is confusing to say the least, so many nested if statements, it's hard to know where it is going wrong, perhaps you should simplify the implementation into seperate cases, thus your nesting would be cut to a minimum, or call methods based on these results, making their order easier to understand.
if (result == -999) {
				String temp = strArray[0];
				strArray[0] = str;
				reorderArray(1, temp);
				count++;
			}


this entire segment seems redundant, is it not handled by a general case? using static return values is never a good way to go.
Was This Post Helpful? 0
  • +
  • -

#3 shezzy  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 194
  • Joined: 28-January 07

Re: List binary search program

Posted 05 April 2007 - 08:54 AM

well it may seem confusing but the check is used every time the add is called, to know where to add it to the array. the teacher wants us to use a system for int return of -#'s if thats where item belong and isnt current in array or +#'s if the item is in the array the index return is the index where it is found. i made another case since if the program would return 0 instead of a dummy value i.e. -999 ( if the item belongs in the beginning of list but isnt currently in the array) then it would think that the item already exists in the list at index 0. it may be confusing but i think it could work

This post has been edited by shezzy: 05 April 2007 - 08:55 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1