I've been tasked with creating a method that will print all the indices where value x is found in a sorted array.

I understand that if we just scanned through the array from 0 to N (length of array) it would have a running time of O(n) worst case. Since the array that will be passed into the method will be sorted, I'm assuming that I can take advantage of using a Binary Search since this will be O(log n). However, this only works if the array has unique values. Since the Binary Search will finish after the first "find" of a particular value. I was thinking of doing a Binary Search for finding x in the sorted array, and then checking all values before and after this index, but then if the array contained all x values, it doesn't seem like it would be that much better.

I guess what I'm asking is, is there a better way to find all the indices for a particular value in a sorted array that is better than O(n)?

```
public void PrintIndicesForValue42(int[] sortedArrayOfInts)
{
// search through the sortedArrayOfInts
// print all indices where we find the number 42.
}
```

Ex: sortedArray = { 1, 13, 42, 42, 42, 77, 78 } would print: "42 was found at Indices: 2, 3, 4"

Well, if you actually do have a sorted array, you can do a binary search until you find one of the indexes you're looking for, and from there, the rest should be easy to find since they're all next to each-other.

once you've found your first one, than you go find all the instances before it, and then all the instances after it.

Using that method you should get roughly **O(lg(n)+k)** where **k** is the number of occurrences of the value that you're searching for.

EDIT:

And, No, you will never be able to access all **k** values in anything less than **O(k)** time.

**Second edit:** so that I can feel as though I'm actually contributing something useful:

Instead of just searching for the first and last occurrences of X than you can do a binary search for the first occurence and a binary search for the last occurrence. which will result in **O(lg(n))** total. once you've done that, you'll know that all the between indexes also contain X(assuming that it's sorted)

You can do this by searching checking if the value is equal to **x** , **AND** checking if the value to the left(or right depending on whether you're looking for the first occurrence or the last occurrence) is equal to **x**.

A Hashmap might work, if you're not required to use a binary search.

Create a HashMap where the `Key`

is the value itself, and then value is an array of indices where that value is in the array. Loop through your array, updating each array in the HashMap for each value.

Lookup time for the indices for each value will be ~ O(1), and creating the map itself will be ~ O(n).

```
public void printCopies(int[] array)
{
HashMap<Integer, Integer> memberMap = new HashMap<Integer, Integer>();
for(int i = 0; i < array.size; i++)
if(!memberMap.contains(array[i]))
memberMap.put(array[i], 1);
else
{
int temp = memberMap.get(array[i]); //get the number of occurances
memberMap.put(array[i], ++temp); //increment his occurance
}
//check keys which occured more than once
//dump them in a ArrayList
//return this ArrayList
}
```

Alternatevely, instead of counting the number of occurances, you can put their indices in a arraylist and put that in the map instead of the count.

```
HashMap<Integer, ArrayList<Integer>>
//the integer is the value, the arraylist a list of their indices
public void printCopies(int[] array)
{
HashMap<Integer, ArrayList<Integer>> memberMap = new HashMap<Integer, ArrayList<Integer>>();
for(int i = 0; i < array.size; i++)
if(!memberMap.contains(array[i]))
{
ArrayList temp = new ArrayList();
temp.add(i);
memberMap.put(array[i], temp);
}
else
{
ArrayList temp = memberMap.get(array[i]); //get the lsit of indices
temp.add(i);
memberMap.put(array[i], temp); //update the index list
}
//check keys which return lists with length > 1
//handle the result any way you want
}
```

heh, i guess this will have to be posted.

```
int predefinedDuplicate = //value here;
int index = Arrays.binarySearch(array, predefinedDuplicate);
int leftIndex, rightIndex;
//search left
for(leftIndex = index; array[leftIndex] == array[index]; leftIndex--); //let it run thru it
//leftIndex is now the first different element to the left of this duplicate number string
for(rightIndex = index; array[rightIndex] == array[index]; rightIndex++); //let it run thru it
//right index contains the first different element to the right of the string
//you can arraycopy this [leftIndex+1, rightIndex-1] string or just print it
for(int i = leftIndex+1; i<rightIndex; i++)
System.out.println(array[i] + "\t");
```

```
public void PrintIndicesForValue42(int[] sortedArrayOfInts) {
int index_occurrence_of_42 = left = right = binarySearch(sortedArrayOfInts, 42);
while (left - 1 >= 0) {
if (sortedArrayOfInts[left-1] == 42)
left--;
}
while (right + 1 < sortedArrayOfInts.length) {
if (sortedArrayOfInts[right+1] == 42)
right++;
}
System.out.println("Indices are from: " + left + " to " + right);
}
```

This would run in O(log(n) + #occurrences) Read and understand the code. It's simple enough.

You will get the result in O(lg n)

```
public static void PrintIndicesForValue(int[] numbers, int target) {
if (numbers == null)
return;
int low = 0, high = numbers.length - 1;
// get the start index of target number
int startIndex = -1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] > target) {
high = mid - 1;
} else if (numbers[mid] == target) {
startIndex = mid;
high = mid - 1;
} else
low = mid + 1;
}
// get the end index of target number
int endIndex = -1;
low = 0;
high = numbers.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] > target) {
high = mid - 1;
} else if (numbers[mid] == target) {
endIndex = mid;
low = mid + 1;
} else
low = mid + 1;
}
if (startIndex != -1 && endIndex != -1){
for(int i=0; i+startIndex<=endIndex;i++){
if(i>0)
System.out.print(',');
System.out.print(i+startIndex);
}
}
}
```

```
Find_Key(int arr[], int size, int key){
int begin = 0;
int end = size - 1;
int mid = end / 2;
int res = INT_MIN;
while (begin != mid)
{
if (arr[mid] < key)
begin = mid;
else
{
end = mid;
if(arr[mid] == key)
res = mid;
}
mid = (end + begin )/2;
}
return res;
}
```

Assuming the array of ints is in ascending sorted order; Returns the index of the first index of key occurrence or INT_MIN. Runs in O(lg n).

Below is the java code which returns the range for which the search-key is spread in the given sorted array:

```
public static int doBinarySearchRec(int[] array, int start, int end, int n) {
if (start > end) {
return -1;
}
int mid = start + (end - start) / 2;
if (n == array[mid]) {
return mid;
} else if (n < array[mid]) {
return doBinarySearchRec(array, start, mid - 1, n);
} else {
return doBinarySearchRec(array, mid + 1, end, n);
}
}
/**
* Given a sorted array with duplicates and a number, find the range in the
* form of (startIndex, endIndex) of that number. For example,
*
* find_range({0 2 3 3 3 10 10}, 3) should return (2,4). find_range({0 2 3 3
* 3 10 10}, 6) should return (-1,-1). The array and the number of
* duplicates can be large.
*
*/
public static int[] binarySearchArrayWithDup(int[] array, int n) {
if (null == array) {
return null;
}
int firstMatch = doBinarySearchRec(array, 0, array.length - 1, n);
int[] resultArray = { -1, -1 };
if (firstMatch == -1) {
return resultArray;
}
int leftMost = firstMatch;
int rightMost = firstMatch;
for (int result = doBinarySearchRec(array, 0, leftMost - 1, n); result != -1;) {
leftMost = result;
result = doBinarySearchRec(array, 0, leftMost - 1, n);
}
for (int result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n); result != -1;) {
rightMost = result;
result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n);
}
resultArray[0] = leftMost;
resultArray[1] = rightMost;
return resultArray;
}
```

It is using Modified Binary Search. It will be O(LogN). Space complexity will be O(1). We are calling BinarySearchModified two times. One for finding start index of element and another for finding end index of element.

```
private static int BinarySearchModified(int[] input, double toSearch)
{
int start = 0;
int end = input.Length - 1;
while (start <= end)
{
int mid = start + (end - start)/2;
if (toSearch < input[mid]) end = mid - 1;
else start = mid + 1;
}
return start;
}
public static Result GetRange(int[] input, int toSearch)
{
if (input == null) return new Result(-1, -1);
int low = BinarySearchModified(input, toSearch - 0.5);
if ((low >= input.Length) || (input[low] != toSearch)) return new Result(-1, -1);
int high = BinarySearchModified(input, toSearch + 0.5);
return new Result(low, high - 1);
}
public struct Result
{
public int LowIndex;
public int HighIndex;
public Result(int low, int high)
{
LowIndex = low;
HighIndex = high;
}
}
```

Similar Questions

Example: Array1.Intersect(Array2) checks for only distinct elements. Is there an elegant way using linq to get the result which contains even duplicates? The result should be case-insensitive. Thanks.

I run the following code which is Insertion Sort algorithm that use binary search to find the right position of the item being inserted instead of linear search but there are two numbers in the result

I have been looking this for hours but i can not find a code which i want. for example array is : 45 16 22 51 18 72 33 64 40 binary must be : 45 16 0 22 0 72 0 0 18 33 0 0 64 0 0 0 0 It puts accordin

Using an algorithm Tree-Insert(T, v) that inserts a new value v into a binary search tree T, the following algorithm grows a binary search tree by repeatedly inserting each value in a given section of

I have an array of strings which is sorted by default. I want a binary search over this list in java. Is there any buit-in binary search function for strings in java?

The requirement is to search an alphabetically ordered/sorted list (of string type) using a binary search method for a specified string (in the example below it is yz) and return the results (every

for a project I need to implement a binary search. This binary search allows duplicates. I have to get all the index values that match my target. I've thought about doing it this way if a duplicate is

I have sorted array {1,2,3,5,5,5,7,8,8} I would like to count how many times the number that i am sending is found in the array in longn only. for example: public static int count(int[] array,5) wil

Hey there I'm using a binary search method to find a number in an array, and I'm getting a StackOverflow error when looking for a number other than the one in the middle. Here is my code: public stati

According to the documentation: public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) Searches the specified array for the specified object using the binary search al

I wrote the following code: def binary_search(key,lst): iterative binary search lst better be sorted for binary search to work n=len(lst) lower=0 upper=n-1 outcome=None # default value while lo

Need help to figure out why the following code for basic Binary Search Tree insertion is not working. Since I have been working on C# for sometime now, I'm afraid I forgot some of my C++. Also, any su

RESOLVED! THANKS EVERYONE. I need to search for duplicates - table as follows: id, q1, q2, q3, text id is unique and I am only interested in finding duplicates where the field text is the same. Any s

I'm trying to write a function that recursively goes through an array, inserting values into a tree while keeping the tree balanced. It's assumed that the array is sorted and that we know its size. I

I created a method which search for duplicates and then stores duplicates index into another array. Then I'm running through my big array and move all entries without duplicates. Now, my problem is th

I have been working with a string[] array in C# that gets returned from a function call. I was wondering what the best way to remove duplicates from this array would be? I could possibly cast to a Gen

I have a homework which ask from me to create a struct of binary search tree where its node of the binary search tree is another binary search tree. The first BST has the Surnames of Students and the

Why is Insertion sort using Binary search is slower than Insertion sort using Linear search? Code for Insertion Sort using Linear search: void InsertionSort(int data[], int size) { int i=0, j=0, temp=

I am trying to create the implementation of a recursive version of my binary search. This is what I have so far. Can anyone help I am not sure how to finish. def binarySearch(searchList, numberSought,

When implementing a Hashtable using an array, we inherit the constant time indexing of the array. What are the reasons for implementing a Hashtable with a Binary Search Tree since it offers search wit

In a binary search, we have two comparisons one for greater than and other for less than, otherwise its the mid value. How would you optimize so that we need to check only once? bool binSearch(int arr

Hi I have an array list which has some numbers in it like {23,16,45,26,2,5,9} and I want to make a binary search tree with this array list which is array and its elements are objects that has 2 fiel

In TreeSet there is a method called contains that returns true if an element is in the set. I assume that this method uses binary search and does not iterate through all the elements in ascending orde

I want to write a loopless program (probably using comprehension) to remove duplicate elements in a sorted array in Python (and most efficiently too).

I have a little confusion in the following two statements. The below program is finds the index of an element out of a sorted array[no duplicates] using binary search. int bin(int *arr,int l,int h,int

Possible Duplicate: Searching a number in a rotated sorted Array I have a sorted array and it has been right rotated N times, where N is unknown. Now I want to do a binary search on it. How can it b

What would be the best way to do a binary search in an array that you can actually access it via indirection? Meaning I have an Integer[] that stores the indexes of a String[] that represent the sorte

I have a ListView of over 1000 items, this list is filterable by a Search function in my Adapter, when clicking on an item it replace the current fragment (The one with the list(A)) with a detail frag

Write a bash script to do a binary search. Read student names and grades from a file into an array. Prompt the user for a student name. Find the name in the array and display the grade. The data in th

I'm learning about binary search and the basic definition starts with an iterator to the first element and another one to the last. You also have a key, which is the element you are looking for. The k

print_r($jobtypes) give me an array. Array contains duplicate elements. I want to remove the duplicates. Here is an array Array ( [0] => stdClass Object ( [term_id] => 40 [name] => Babysitti

I've been reading some binary search algorithms I found on the internet, and I noticed this block of code within all examples I have encountered. if (query > contents[midIndex]) { minIndex = midInd

Possible Duplicates: Merging two sorted lists Algorithm for N-way merge Given k sorted arrays each of length n, construct a single merged and sorted array.focus on running time and space complexity.

I need to create a function that creates a BST from an array, in python. The array is already sorted. The example is: function array_to_binary_search_tree(array, start, end) if start > end Return a

I wrote this function that uses a binary search to look for a specific value in an array of structs. Why doesn't it compile? I'm getting this error: prog.c:224: error: subscripted value is neither ar

Suppose I have a sorted array of integers int[], and I want to search the closest smaller value to some input number. for example if the array contains (1) , (23), (57) , (59), (120) and the input is

Problem: Given a sorted array of integers find the most frequently occurring integer. If there are multiple integers that satisfy this condition, return any one of them. My basic solution: Scan throu

I have seen a lot of search algorithms to search in a binary sorted tree, but all of them are using the same way: recursion. I know recursion is expensive in comparison to loops, because every time we

I am just playing with some STL Algorithms. While using binary_search I am stuck. I have sorted the vector dictionary & then I am running binary_search by writing my own comparator function. Howev

Below is my Generic Binary Search it works ok with the intgers type array it finds all the elements in it . But the Problem Arises when i use a string array to find any string data. It runs ok for the

I was doing the binary search for String and it showing output error. I do not know what I missing and I need some advice. Here my code : public static final int Not_Found = -1; public static int BS(

I need help with binary searching arrays, my problem is that I feel like I have all the right requirements but it's not searching at all. I don't get any error messages. Just not getting the results I

I have in memory an array of 16 byte wide entries. Each entry consists of two 64 bit integer fields. The entries are in sorted order based upon the numerical value of the first 64 bit integer of each

What is the difference between binary search and binary search tree? Are they the same? reading the internet it seams the second is only for trees(up to 2 children nodes) and binary search doesn't fol

I am having a bit of trouble with creating a Binary Search using a templated dynamic array class and iterators. In my class I have the following function that causes an infinite loop. iterator binar

I am implementing a Binary Search tree in C++ I have the following code to add an entry to the tree: void tree::add(int n) { int found; leaf *t,*parent; findparent(n,found,parent); if(found==YES) cout

I am trying to optimize a search through a very short sorted array of doubles to locate a bucket a given value belongs to. Assuming the size of the array is 8 doubles, I have come up with the followin

I was trying on one of the questions on how to find a list of duplicated array. This program works: import java.util.*; public class CheckDuplicates { public static void main(String[]args){ boolean c

I having a problem with coding this: Write a static method named removeDuplicates that takes as input an array of integers and returns as a result a new array of integers with all duplicates removed.

how can i remove duplicates using HashSet or if you have better idea please let me know but so far this is what i am doing... i am trying to eliminate the duplicates and below code is what i am using.