Results 1 to 7 of 7
  1. #1
    Jack_Tauson_Sr is offline Senior Member
    Join Date
    Nov 2011
    Posts
    114
    Rep Power
    0

    Default Didn't understand how Index value is returned.

    Please consider the following program:

    Java Code:
    import java.io.*;
    
    public class RotatedArrayAgain {
    
    	
    	public static void main(String[] args) throws IOException {
    		
    		int[] array = {12,13,15,16,21,3,4,5,6};
    		
    		int len = array.length;
    		
    		System.out.println("Enter the Number to be searched");
    		
    		InputStreamReader in = new InputStreamReader(System.in);
    		BufferedReader bf = new BufferedReader(in);
    		
    		int target = Integer.parseInt(bf.readLine());
    		
    		System.out.println("The Number Entered by the user is : " + target + "\n Let's see if it's there in the Rotated Array or Not :)");
    		
    		int index = RotatedArray(array,len,target);
    		
    		if(index == -1){
    			System.out.println("The Number is not in the ARRAY ! Sorry !");
    		}
    		else
    		{
    			System.out.println("The number is found at the index" + index);
    		}
    		
    	}
    	
    	
    	public static int RotatedArray(int a[], int n , int target){
    		
    		
    		int low = 0,high = a.length-1;
    		
    		while (low <= high){
    			
    			int mid = (low + high)/2;
    			//CASE 1:  If target is the middle element
    			if( target == a[mid]){
    				
    				return mid;
    			}
    			// CASE 2: If the Element is in Right Sorted Array
    			else if (a[mid] <= a[high]){
    				
    				if ( target > a[mid] && target < a[high])
    					low = mid + 1;
    				else
    					high = mid - 1;
    			}
    			// CASE 3: If the Element is in Left Sorted Array
    			else if ( a[low] <= a[mid]){
    				
    				if (target > a[low] && target  < a[mid]){
    					high = mid-1;
    					
    						//low = mid + 1;
    					
    				}else 
    					low = mid+1;
    				
    				
    				
    			}
    			
    			
    			
    		}// END WHILE
    		
    		
    		
    		
    		return -1;
    	}
    	
    	
    
    }
    The output of the above program is as follows:

    Java Code:
    Enter the Number to be searched
    15
    The Number Entered by the user is : 15
     Let's see if it's there in the Rotated Array or Not :)
    The number is found at the index 2
    My Question:

    I didn't understand how the index of the array is getting printed properly in the above problem. My concern is with the following part of the code snippet from the above program:

    Java Code:
    if(index == -1){
    			System.out.println("The Number is not in the ARRAY ! Sorry !");
    		}
    		else
    		{
    			System.out.println("The number is found at the index" + index);
    		}

    Please help !

    Thanks in advance.

  2. #2
    wsaryada is offline Senior Member
    Join Date
    Jun 2007
    Location
    Bali, Indonesia
    Posts
    760
    Rep Power
    8

    Default Re: Didn't understand how Index value is returned.

    I think your RotatedArray method trying to find the index of the target element by dividing the array into two part. The left sorted part and the right sorted part. So it can quickly find the target element. When the target is smaller that the middle element it search to the left. When it bigger it search to the right. It will repeat until the target element found. If not it return -1.

  3. #3
    Jack_Tauson_Sr is offline Senior Member
    Join Date
    Nov 2011
    Posts
    114
    Rep Power
    0

    Default Re: Didn't understand how Index value is returned.

    Thanks for your reply. I did understand that. But I'm not getting how index variable is getting the value of the index?


    Quote Originally Posted by wsaryada View Post
    I think your RotatedArray method trying to find the index of the target element by dividing the array into two part. The left sorted part and the right sorted part. So it can quickly find the target element. When the target is smaller that the middle element it search to the left. When it bigger it search to the right. It will repeat until the target element found. If not it return -1.

  4. #4
    wsaryada is offline Senior Member
    Join Date
    Jun 2007
    Location
    Bali, Indonesia
    Posts
    760
    Rep Power
    8

    Default Re: Didn't understand how Index value is returned.

    Quote Originally Posted by Jack_Tauson_Sr View Post
    Thanks for your reply. I did understand that. But I'm not getting how index variable is getting the value of the index?
    Because the RotatedArray() method return a value. Is that what you want to know?

  5. #5
    Jack_Tauson_Sr is offline Senior Member
    Join Date
    Nov 2011
    Posts
    114
    Rep Power
    0

    Default Re: Didn't understand how Index value is returned.

    I understand that "int index = RotatedArray(array,len,target);", that is index is getting some value from the method RotatedArray but if we consider Case 2 and 3, I haven't specified any return statement just like in Case 1 where I'm returning mid explicitly. This is what I'm not understanding. Please clarify.



    Quote Originally Posted by wsaryada View Post
    Because the RotatedArray() method return a value. Is that what you want to know?

  6. #6
    wsaryada is offline Senior Member
    Join Date
    Jun 2007
    Location
    Bali, Indonesia
    Posts
    760
    Rep Power
    8

    Default Re: Didn't understand how Index value is returned.

    I suggest that you try to simulate the code using pencil and paper. Write down the value of every variable you have there for each steps in the loop. In a quick look what I can see that the case 2 and case 3 modify the value of low and high. Which will give a changing the value of mid variable in the next loop. And at some point this will make the case 1 become true (target == a[mid]) and return mid as the found index. Otherwise you method will return -1.

    So get a pencil and paper and trace your code.

  7. #7
    Jack_Tauson_Sr is offline Senior Member
    Join Date
    Nov 2011
    Posts
    114
    Rep Power
    0

    Default Re: Didn't understand how Index value is returned.

    I think you are right. I should do that. Thanks for your reply.

    Quote Originally Posted by wsaryada View Post
    I suggest that you try to simulate the code using pencil and paper. Write down the value of every variable you have there for each steps in the loop. In a quick look what I can see that the case 2 and case 3 modify the value of low and high. Which will give a changing the value of mid variable in the next loop. And at some point this will make the case 1 become true (target == a[mid]) and return mid as the found index. Otherwise you method will return -1.

    So get a pencil and paper and trace your code.

Similar Threads

  1. jbuttons and jcombobox didn't show up please help...
    By jackwong in forum New To Java
    Replies: 3
    Last Post: 06-08-2012, 05:48 PM
  2. Replies: 5
    Last Post: 09-17-2011, 02:35 AM
  3. Replies: 0
    Last Post: 10-29-2010, 09:15 PM
  4. My own ClassLoader didn't work.
    By snooze-g in forum Advanced Java
    Replies: 1
    Last Post: 07-17-2007, 12:12 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •