Sorting an array and using binary search

Question

I've already gotten this program to run and it almost gives me the answer I want. After running the whole program, it's supposed to print out the index of the key and what the key is equal too. I cannot for the life of me figure out how to get the index into the final message in the console. For example, if you have an array of {0,1,2,3,4,5,6,7,8,9} and your key is 0, it's supposed to return: list[0] = 0. I labeled the part I think where my problem lies with "(index???)"

import java.util.Scanner;
public class PartA {
    public static void main(String[] args){
        System.out.println("Please enter 10 double values:");
        double [] array = inputArray();
        selectionSort(array);
        printArray(array);
        System.out.println("Please enter a search key:");
        Scanner input = new Scanner(System.in);
        double key = input.nextDouble();
        double x = binarySearch(array,key);
        if (x != -1)
            System.out.println("list[" + (index???) + "] = " + key);
        else
            System.out.println(key + " is not on the list");
        }

        public static double[] inputArray(){
            Scanner array = new Scanner(System.in);
            double [] list = new double[10];
            for(int i = 0; i < list.length; i++){
                array.hasNextDouble();
                list[i] = array.nextDouble();
            }
            return list;
        }
        public static void selectionSort(double[] list){            
            double array[] = new double [list.length];
            for(int i = 0; i < list.length; i++){
                for(int j = 0; j < list.length; j++){
                    if (list[i] < list[j]){
                        double x = list[i];
                        list[i] = list[j];
                        list[j] = x;
                    }
                }
            }
        }
        public static void printArray(double[] list){
            for (int i = 0; i < list.length; i++){
                System.out.println("list[" + i + "] = " + list[i]);
            }
            System.out.println();
        }
        public static int binarySearch(double []list, double key){
            int low = 0, high = list.length - 1;
            while(high >= low){
            int mid = (low + high)/2;
            if(key < list[mid])
                high = mid - 1;
            else if(key == list[mid])
                return mid;
            else low = mid + 1;
            }
            return -1;
        }
}

The problem is that the index which was returned is not correct? Or what is the problem? — Zelldon
– Zelldon, Commented Apr 9, 2015 at 6:42
binarySearch() returns the index of the key in the array, right? And you've stored this index in the variable x, right? So what do you conclude? Why is x declared as double, since it's supposed to represent an index in an array? Why do you call it xrather than... index? — JB Nizet
– JB Nizet, Commented Apr 9, 2015 at 6:43
I believe you want the index from the original array, right? Your question is not formed correctly! If the value in index 0 is 0 in your question, how is one supposed to understand which is which? Moreover, you are sorting the array in your program, but for your sample input, you have given a sorted array. Please modify you question for better understanding your problem. — inquizitive
– inquizitive, Commented Apr 9, 2015 at 6:46
Use: int idx = binarySearch(array,key); and later for the printing: System.out.println("list[" + idx + "] = " + key); — Zelldon
– Zelldon, Commented Apr 9, 2015 at 6:46

Zelldon · Accepted Answer · 2015-04-09 07:11:00Z

1

I also mentioned already in the comments of the Question the solution, but for the sake of completeness i post this answer.

public class Main {
    public static void main(String[] args){
        System.out.println("10 double values:");
        double [] array = {0,1,2,3,4,5,6,7,8,9};
        selectionSort(array);
        printArray(array);
        double key = 4;
        System.out.println("Searched Key: " + key);
        int idx = binarySearch(array,key); //use int instead of double
        if (idx != -1)
            //use the variable identifier to print the index
            System.out.println("list[" + idx + "] = " + key); 
        else
            System.out.println(key + " is not on the list");
        }

        public static void selectionSort(double[] list){            
            double array[] = new double [list.length];
            for(int i = 0; i < list.length; i++){
                for(int j = 0; j < list.length; j++){
                    if (list[i] < list[j]){
                        double x = list[i];
                        list[i] = list[j];
                        list[j] = x;
                    }
                }
            }
        }
        public static void printArray(double[] list){
            for (int i = 0; i < list.length; i++){
                System.out.println("list[" + i + "] = " + list[i]);
            }
            System.out.println();
        }
        public static int binarySearch(double []list, double key){
            int low = 0, high = list.length - 1;
            while(high >= low){
            int mid = (low + high)/2;
            if(key < list[mid])
                high = mid - 1;
            else if(key == list[mid])
                return mid;
            else low = mid + 1;
            }
            return -1;
        }
}

Working example with Ideone: http://ideone.com/WXrJPi

answered Apr 9, 2015 at 7:11

Zelldon

5,5013 gold badges37 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

inquizitive Over a year ago

So if the input is double [] array = {1,2,4,6,3,5,0,7,8,9}; instead of being entered in an already sorted manner, the response is exactly same! What is the point of showing the index, if it is different from the input of the user?

Zelldon Over a year ago

I used the defined array to show the algorithm and the his problem, because ideone not accept the user input from System.in.

inquizitive Over a year ago

You did not get my question. My question is, the output of the program with my input shows list[4]=4, but that is wrong, since evidently 4 is at index 3 in my input. The problem is that the indexes are all messed up since the original array is being sorted. That is why, initially I asked the question, whether the OP wants the index from the original array which was input or not!

Zelldon Over a year ago

Binary search is only possible on already sorted data, if you want to find a key with the idx which it has originally use brute force. Or you save the original idx in a map. Besides i didnt ask the question so i dont know why he wants the idx of the sorted array.

v1shnu · Accepted Answer · 2015-04-09 06:55:29Z

0

I think your code works perfect. You just have to replace (index???) with x and change the type of x from double to int so that is does not print the the value as a double value.

 int x = binarySearch(array,key);
 if (x != -1)
 System.out.println("list[" + (x) + "] = " + key);
 else
 System.out.println(key + " is not on the list");
 }

Output:

Please enter 10 double values:
0
1
2
3
4
5
6
7
8
9
list[0] = 0.0
list[1] = 1.0
list[2] = 2.0
list[3] = 3.0
list[4] = 4.0
list[5] = 5.0
list[6] = 6.0
list[7] = 7.0
list[8] = 8.0
list[9] = 9.0

Please enter a search key:
5
list[5] = 5.0

answered Apr 9, 2015 at 6:55

v1shnu

2,24110 gold badges45 silver badges72 bronze badges

Collectives™ on Stack Overflow

Sorting an array and using binary search

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related