Open In App

Arrays.binarySearch() in Java with examples | Set 2 (Search in subarray)

Last Updated : 30 Mar, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Arrays.binarySearch()| Set 1 Covers how to find an element in a sorted array in Java. This set will cover “How to Search a key in an array within a given range including only start index”.

Syntax :  

public static int binarySearch(data_type[] arr, int fromIndex, int toIndex, data_type key)

Parameters :

arr – the array to be searched

fromIndex – the index of the first element (inclusive) to be searched

toIndex – the index of the last element (exclusive) to be searched

 key  – the value to be searched for 

  • It is a static inbuilt method defined in Arrays (java.util.Arrays) class in java and returns the index of the specified key is found within the specified range.
  • Here, data_type can be any of the primitive data_type: byte, char, double, int, float, short, long and Object as well.
  • The above function Searches a range of the specified array of the given data type for the specified key using a binary search algorithm.
  • The range within which the specified key to be searched must be sorted (as by the Arrays.sort() method) prior to making this call. Otherwise, the result would be undefined. If the specified array contains multiple values same as the specified key, there is no guarantee which one will be found.

Returns : 
Index of the specified key is found within the specified range in the specified array, Otherwise (-(insertion point) – 1). 

The insertion point is defined as a point at which the specified key would be inserted: the index of the first element in the range greater than the key, or toIndex if all elements in the range are less than the specified key. 
Note: This guarantees that the return value will be >= 0 if and only if the key is found.

Examples:  

   byteArr[] = {10,20,15,22,35}

   key = 22 to be searched between the range 2 to 4 in specified array.

   Output: 3

   charArr[] = {‘g’,’p’,’q’,’c’,’i’}

   key = p to be searched between the range 1 to 4 in specified array.

   Output: 3

   intArr[] = {1,2,3,4,5,6}

   key = 3 to be searched between the range 1 to 4 in specified array.

   Output: 2

   doubleArr[] = {10.2,1.51,2.2,3.5}

   key = 1.5 to be searched between the range 1 to 4 in specified array.

   Output: -2 as it is the insertion point of 1.5

   floatArr[] = {10.2f,15.1f,2.2f,3.5f}

   key = 35.0 to be searched between the range 1 to 4 in specified array.

   Output: -5

  shortArr[] = {10,20,15,22,35}

  key = 5 to be searched between the range 0 to 4 in specified array.

  Output: -1

Implementation :
 

Java




// Java program to demonstrate working of  binarySearch()
// method for specified range in a sorted array.
import java.util.Arrays;
 
public class GFG {
    public static void main(String[] args)
    {
        byte byteArr[] = { 10, 20, 15, 22, 35 };
        char charArr[] = { 'g', 'p', 'q', 'c', 'i' };
        int intArr[] = { 1, 2, 3, 4, 5, 6 };
        double doubleArr[] = { 10.2, 15.1, 2.2, 3.5 };
        float floatArr[] = { 10.2f, 15.1f, 2.2f, 3.5f };
        short shortArr[] = { 10, 20, 15, 22, 35 };
 
        Arrays.sort(byteArr);
        Arrays.sort(charArr);
        Arrays.sort(intArr);
        Arrays.sort(doubleArr);
        Arrays.sort(floatArr);
        Arrays.sort(shortArr);
 
        byte byteKey = 22;
        char charKey = 'p';
        int intKey = 3;
        double doubleKey = 1.5;
        float floatKey = 35;
        short shortKey = 5;
 
        System.out.println(
            byteKey + " found at index = "
            + Arrays.binarySearch(byteArr, 2, 4, byteKey));
        System.out.println(
            charKey + " found at index = "
            + Arrays.binarySearch(charArr, 1, 4, charKey));
        System.out.println(
            intKey + " found at index = "
            + Arrays.binarySearch(intArr, 1, 4, intKey));
        System.out.println(doubleKey + " found at index = "
                           + Arrays.binarySearch(
                               doubleArr, 1, 4, doubleKey));
        System.out.println(floatKey + " found at index = "
                           + Arrays.binarySearch(
                               floatArr, 1, 4, floatKey));
        System.out.println(shortKey + " found at index = "
                           + Arrays.binarySearch(
                               shortArr, 0, 4, shortKey));
    }
}
 






                        










Output


22 found at index = 3
p found at index = 3
3 found at index = 2
1.5 found at index = -2
35.0 found at index = -5
5 found at index = -1




Complexity Analysis:


Time Complexity:
The time complexity of the binarySearch() method in the Arrays class is O(log n) for searching within a specified range. In the given code, the binarySearch() method is called six times, each time with a different array and a different range of elements. Therefore, the time complexity of the entire code would be O(log n) * 6, which can be simplified to O(log n).


Auxiliary Space:
The binarySearch() method does not use any additional space. Therefore, the auxiliary space complexity of the code is O(1).


Exceptions :  


    

  1. IllegalArgumentException : throws when starting index(fromIndex) is greater than the end index(toIndex) of specified range.(means: fromIndex > toIndex)
    2. 

  2. ArrayIndexOutOfBoundsException : throws if one or both index are not valid means fromIndex<0 or toIndex > arr.length.
    3. 



Important Points:  


    

  • If the input list is not sorted, the results are undefined.
    • 

  • If there are duplicates, there is no guarantee which one will be found.
    • 



Reference : 


https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(int[],%20int)








                                    


                                                                        

                                        

                                            

                                                

                                                    
N
                                                

                                                

                                                    



    Nitsdheerendra



                                                

                                            

                                                                                    

                                        

                                            
    

        
        
    
                                            

                                                
                                                
                                            

                                            

                                            Improve
                                                
                                            

                                        

                                    



                            

                                                            

                                    
                                        
                                        Previous Article
                                    
                                    
                                    

                                        Arrays.binarySearch() in Java with examples | Set 1
                                    

                                

                                                            

                                    
                                        Next Article
                                        
                                    
                                    
                                    

                                        Collections.binarySearch() in Java with Examples
                                    

                                

                                                        

                            

            

                

                    

                    
                
 
                
    
                            

                                

                            


                            


            

        
  
                        

                                                

                        
                                                    

                                
Similar Reads

                                

                                    
        
            

                
Arrays.binarySearch() in Java with examples | Set 1

                
Arrays.binarySearch() method searches the specified array of the given data type for the specified value using the binary search algorithm. The array must be sorted as by the Arrays.sort() method prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no g

            

            
            

                
                5 min read
            

        
    
        
            

                
Collections.binarySearch() in Java with Examples

                
java.util.Collections.binarySearch() method is a java.util.Collections class method that returns position of an object in a sorted list. // Returns index of key in sorted list sorted in // ascending order public static int binarySearch(List slist, T key) // Returns index of key in sorted list sorted in // order defined by Comparator c. public stati

            

            
            

                
                4 min read
            

        
    
        
            

                
Java.util.Arrays.parallelSetAll(), Arrays.setAll() in Java

                
Prerequisites : Lambda Expression in Java 8IntUnaryOperator Interface parallelSetAll and setAll are introduced in Arrays class in java 8. parallelSetAll(): It set all the element in the specified array in parallel by the function which compute each element. Syntax: public static void parallelSetAll(double[] arr, IntToDoubleFunction g) Parameters :

            

            
            

                
                5 min read
            

        
    
        
            

                
Java Program to Search ArrayList Element Using Binary Search

                
Linear Search can be implemented for sorting and non-sorting elements of a Data structure particular Data structure but the average case time complexity is O(n). Whereas as Binary Search can be implemented only when the items are in sorted order and average-case time complexity is O(logn) and both Transversal have best-case Time complexity is O(1).

            

            
            

                
                3 min read
            

        
    
        
            

                
Java Program to Search User Defined Object From a List By Using Binary Search Using Comparator

                
The Comparator interface in Java can be used to compare user-defined objects. The Comparator interface is present in java.util package. Binary search is a searching algorithm that uses the divide and conquers rule to search the presence of an element in a list or array. The binary search algorithm works only on a sorted list. In case the list is no

            

            
            

                
                6 min read
            

        
    
        
            

                
Java.util.Arrays.equals() in Java with Examples

                
Today we are going to discuss the simplest way to check whether two arrays are equal or not. Two arrays are considered equal if both arrays contain the same number of elements, and all corresponding pairs of elements in the two arrays are equal. In other words, two arrays are equal if they contain the same elements in the same order. Also, two arra

            

            
            

                
                4 min read
            

        
    
        
            

                
Difference Between Arrays.toString() and Arrays.deepToString() in Java

                
The deepToString() method of the Arrays class returns the string representation of the deep contents of the specified Object array. Unlike Arrays. toString(), if the array contains other arrays as elements, the string representation includes their contents, and so on. Arrays.toString(): Returns a string representation of the contents of the specifi

            

            
            

                
                3 min read
            

        
    
        
            

                
Java 8 | Arrays parallelSort() method with Examples

                
Java 8 introduced a new method called as parallelSort() in java.util.Arrays Class. It uses Parallel Sorting of array elements Algorithm of parallelSort() 1. The array is divided into sub-arrays and that sub-arrays is again divided into their sub-arrays, until the minimum level of detail in a set of array. 2. Arrays are sorted individually by multip

            

            
            

                
                4 min read
            

        
    
        
            

                
Arrays asList() method in Java with Examples

                
The asList() method of java.util.Arrays class is used to return a fixed-size list backed by the specified array. This method acts as a bridge between array-based and collection-based APIs, in combination with Collection.toArray(). The returned list is serializable and implements RandomAccess. Tip: This runs in O(1) time. Syntax: public static List

            

            
            

                
                3 min read
            

        
    
        
            

                
util.Arrays vs reflect.Array in Java with Examples

                
Array class in java.lang.reflect package is a part of the Java Reflection. This class provides static methods to create and access Java arrays dynamically. It is a final class, which means it can’t be instantiated or changed. Only the methods of this class can be used by the class name itself. On the other hand, Arrays class in java.util package is

            

            
            

                
                2 min read
            

        
                                    

                                                                    
                                                            

                        

                        

                                                            

                                    
Article Tags : 

                                    
                                                                            
                                                                    

                                                                                        

                                    
Practice Tags : 

                                    
                                                                    

                                                    

                                                

                                

                                    
                                                                    

                            


                        

                            

                                                                                    

                              

                            

                                                        
                        

                    

                

            

        
        


        

                




	
	
	

	
	

	
	    

	
	

	
	



                
        

    

    

        

            

            

        

    















	

    
  

  
  








    
        We use cookies to ensure you have the best browsing experience on our website. By using our site, you
        acknowledge that you have read and understood our
        Cookie Policy &
        Privacy Policy
            
    







   Lightbox