Vector is a legacy class in Java and is present from Java 1.2 version. It implements the List interface of the Collection framework and is found in java.util package. Vector is just like an array that can grow dynamically. Vectors are synchronized ie vectors are thread-safe. Vectors are mainly used where thread synchronization is of utmost importance. In other cases, ArrayList performs better. Since vector is a legacy class in Java, the elements in a vector can be iterated over by Enumeration only. In this article, we shall see a binary search operation on a vector. Binary search is a search technique in which a sorted array is repeatedly divided into half and the middle element is checked for the target element. To search a target element in a vector we will be using the binarySearch() method of the Collections class.
Syntax:
binarySearch(List list, Object target)
Parameters:
- The List type object on which binary search is to be performed.
- The value of the target element.
Return Value: Returns the index of the target element if it is found else returns -1.
Example:
Java
// Java Program to Demonstrate Binary Search on Vector// Importing utility classesimport java.util.*;// Main class// BinarySearchOnVectorclass GFG { // Main driver method public static void main(String[] args) { // Creating a Vector by // declaring integer object of Vector class Vector<Integer> v = new Vector<>(); // Adding elements to Vector // using add() method v.add(10); v.add(50); v.add(20); v.add(40); v.add(25); // Note: Binary search works only on sorted list // Sorting the above vector // using sort() method of Collections class Collections.sort(v); // Searching an element using binarySearch() method // of Collections class int index = Collections.binarySearch(v, 25); // Printing the position of the target System.out.println("Element is found at index : " + index); }} |
Element is found at index : 2
Output Explanation: The vector elements were not added in the sorted order. Since binary search works only on the sorted list, we sort the vector first and then perform a binary search. The target is found at index 2 and hence the value is returned and printed.
Time Complexity: O(log n) where ‘n’ is the size of the vector.
Example 2:
Java
// Java Program to Demonstrate Binary Search on Vector// Importing required classesimport java.util.*;// Main class// BinarySearchVectorclass GFG { // Main driver method public static void main(String[] args) { // Creating a Vector by // declaring object of Vector class of string type Vector<String> v = new Vector<>(); // Adding elements to Vector // using add() method v.add("10"); v.add("B"); v.add("20"); v.add("A"); v.add("25"); // Note: Binary search works only on sorted list // Sorting the above vector elements using // sort() of Collections class Collections.sort(v); // Printing the sorted elements of above vector System.out.println("Sorted Vector: " + v); // Searching an element using binarySearch method // of Collections class int index = Collections.binarySearch(v, "25"); // Printing the position of target on console System.out.println("Element is found at index : " + index); }} |
Sorted Vector: [10, 20, 25, A, B] Element is found at index : 2
Output explanation: The numeric strings are positioned before the alphabetic strings. Now the target string 25 lies at index 2 and hence the value is returned and printed.
Time Complexity: O(log n) where ‘n’ is the size of the vector.
