0% found this document useful (0 votes)
22 views2 pages

Java Binary Search and HashMap Example

The document contains Java code for two functionalities: a binary search algorithm that returns the indices of all occurrences of a target value in a sorted array, and a HashMap demonstration that shows how to add, update, retrieve, and remove key-value pairs. The binary search implementation includes logic to find all instances of the target both before and after the mid-point. The HashMap section illustrates basic operations such as checking for keys, retrieving values, and iterating through entries.

Uploaded by

u2204049
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
22 views2 pages

Java Binary Search and HashMap Example

The document contains Java code for two functionalities: a binary search algorithm that returns the indices of all occurrences of a target value in a sorted array, and a HashMap demonstration that shows how to add, update, retrieve, and remove key-value pairs. The binary search implementation includes logic to find all instances of the target both before and after the mid-point. The HashMap section illustrates basic operations such as checking for keys, retrieving values, and iterating through entries.

Uploaded by

u2204049
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Java Binary search code with occurrence idx return

public static void main(String[] args) {

int[] array = { 1, 2, 3, 4, 5, 6, 6, 7 ,8 ,9};


int target = 11;
int[] indices = new int[[Link]] ;

int count = 0;

int low =0, high = [Link]-1;

while(low <= high ) {


int mid = low+(high-low)/2;
if(array[mid] == target) {
for (int i = mid; i >= 0 && array[i] == target;i-- ) {
indices[count++] = i;
}
for (int i = mid+1; i < [Link] && array[i] == target; i++) {
indices[count++] = i;
}
break;
}
else if ( array[mid] > target) {
high = mid-1;
}
else
low = mid+1;
}

if (count!=0) {
[Link]("Target is found at: ");
for(int i = 0; i< count;i++) {
[Link](indices[i]+" ");
}
}
else [Link]("Target not found.");
}

HashMap
import [Link];
import [Link];
import [Link];

public class Main{


public static void main(String[] args) {
HashMap<String, Double> map = new HashMap<>();

[Link]("Minju", 3.71); // adds a new pair if it didn't exist b4


[Link]("Poushi", 3.65); // updates values if key is same
[Link]("Nishat", 3.82); // add as new pair id value is same
[Link]("A", 3.45);

[Link](map);
[Link]([Link]("Minju"));
[Link]([Link](3.65));
[Link]([Link]("Minju")); // get(key) -> returns valur of that key
[Link]();

//getting pairs using iterator


for ( [Link]<String, Double> e : [Link]() ) {
[Link]([Link]() + " "+ [Link]());
}
[Link]();
// using a set of keys
Set<String> keys = [Link]();
for (String key: keys) {
[Link](key +" "+ [Link](key));
}
[Link]("A"); // remove using key
[Link]([Link]()); //returns the number of (key, value) pairs
}
}

Common questions

Powered by AI

Including negative numbers in the array would not inherently affect the binary search code's execution algorithmically, as long as the array remains sorted. However, if negative values reverse the sorting order unintentionally or cause confusion about position indices, the search logic might fail. It is crucial to ensure the array's numerical order beforehand. No changes are necessary if the order is maintained, as the algorithm operates on index positions, not values themselves. Adjustments should focus on maintaining correct sorting post any updates to the dataset.

Calculating 'mid' as 'low + (high - low) / 2' instead of '(low + high) / 2' is significant in avoiding overflow errors. In high values of 'low' and 'high', their sum could exceed the maximum value an integer can store, causing incorrect behavior due to integer overflow. This refined calculation prevents such problems and is a safer, more robust way to compute the middle index, especially in large arrays or datasets.

The given binary search code is structured to find the initial occurrence of the target at 'mid' and then uses two loops: one to iterate backwards from 'mid' and one to iterate forward. These loops add indices to the array 'indices' for each occurrence of the target value found both before and after the initial 'mid' index. If the array had duplicate target values, these loops would successfully collect all occurrences in 'indices'. However, since the array is sorted, these duplicates need to be consecutive for this approach to work fully in capturing all indices.

The HashMap in the Java program is used to store elements as key-value pairs where keys are strings (names) and values are doubles (numerical grades). The `map.put` method adds or updates pairs; it will update the value if the same key exists. `map.containsKey` checks if a key exists, and `map.containsValue` checks for a specific value's presence. `map.get` retrieves a value using its key. Iterating over `map.entrySet()` or using a `keySet()` retrieves keys with their associated values. Finally, `map.remove` deletes a pair using its key. After manipulation, `map.size()` returns the number of pairs present.

The binary search method is efficient for finding a target in a sorted array due to its O(log n) time complexity, which arises from dividing the search interval in half with each iteration. This efficiency allows it to quickly locate a target value without needing to check each element sequentially. However, the limitation in this code is evident in its approach to duplicates. If the target value exists multiple times, additional logic is required to capture all occurrences accurately, which is included here with backward and forward scanning from the first instance found. Furthermore, binary search is effective only on arrays that are already sorted.

If a key already exists in the HashMap and a new put operation is performed with that same key, the existing key's value is overwritten by the new value provided. This behavior is beneficial for maintaining the uniqueness of keys in a HashMap, ensuring that each key is associated with only one value at any time. It provides a straightforward mechanism to update values associated with specific keys without the need to remove and re-insert keys.

If a new entry ("Alex", 3.9) is added to the HashMap and then iterated using entrySet, the output will display all key-value pairs line by line, including the new entry. The results will therefore be similar to: Minju 3.71 Poushi 3.65 Nishat 3.82 A 3.45 Alex 3.9. However, note "A" will be excluded if map.remove("A") is called after adding Alex.

The binary search code will not find the target value 11 in the provided array because 11 doesn't exist within the elements of the array {1, 2, 3, 4, 5, 6, 6, 7, 8, 9}. Since binary search operates by continuously dividing the array in half until the target is found or the low index surpasses the high index, and since 11 is greater than all elements in the array, the search will terminate without finding the target. As a result, the count remains zero, and it prints 'Target not found.'

The Java code illustrates Java's built-in data structures' flexibility and capabilities by leveraging both arrays and HashMaps for different tasks. Arrays are used with binary search for their innate compatibility with efficient searching algorithms due to their ordered indexing. Meanwhile, HashMaps demonstrate dynamic data handling, key-value pair storage, and quick retrieval capability evident in various operations like adding, updating, checking existence, and removing entries. This dual usage showcases Java’s powerful standard libraries that provide efficient solutions for a broad range of algorithmic problems, adaptable to both simple linear structures and complex associative arrays.

After removing the entry with key "A" from the HashMap, the `map.size()` method will report a size of 3. This reflects that HashMap operations are dynamically adjustable—entries can be added, modified, or removed, which changes the size of the map accordingly. The size function provides a direct count of currently active key-value pairs, showing the HashMap's state at any given time.

You might also like