Category Archives: Search

Searching for an element in array of adjacent numbers

Given an array of numbers where the difference between any adjacent numbers is 1, how do we efficiently find a given number?

For example consider the array {1, 2, 1, 2, 3, 2, 3, 4, 5, 6}, and we want to search for the number 5.

The simplest solution is to check if the number is present or not using linear search. This algorithm takes O(n) time in the worst case.
But we are not utilizing the fact that the adjacent numbers differ by 1.

How do we utilize this property to improve the performance?

Let us assume we are searching for a number x+3 in an array.
Let us start with a number x at index 0. Here are the some of the possible patterns of numbers that the array can have

x, x+1, x+2, x+3, ...
x, x+1, x, x+1, ...
x, x-1, x, x+1, ...
x, x-1, x-2, x-1, ...
x, x+1, x+2, x+1, ...
etc...

We can safely jump to index 3 and check if the number is present. Why? Because in any pattern there is no chance of having x+3 before the index 3.
If the number is present, that is fine. Otherwise repeat the same procedure until we find the element or reach the end of the array.

The time complexity of the above procedure is still O(n), because in the worst case, we make n/2 jumps. But this is an improvement over the linear search (n comparisons in the worst case).

Example, search for number 6 in the array {4, 5, 4, 5, 4, 5, 4, 5, 4, 5}, we have to make 5 jumps to conclude that 6 is not present.

Here is the C++ implementation of the same.

Linear search

Given an array of numbers, how do we search for a given number?

For example, given an array [6, 50, 24, 36, 42], the number 36 is present at the index 3 starting with 0. The number 17 is not present any where.

The simplest algorithm to solve this problem is to check each element of the array starting from the first element and search till the target element is found or we reach the end of the array. This most fundamental algorithm is called the linear search.

Here is the pseudo code for the same.

ind = 0 
while ind < length(Array)
   if Array[ind] == target     
      print ind
      break   
   ind = ind + 1 
print -1

Searching for a word in a grid

Given a two dimensional table of letters, and a word to be searched, design an algorithm to check if it is present in the grid.
The word can be formed in any of the 8 possible directions as shown below.

Here is how I solved this problem.

Write a function which takes the string to be searched, the starting coordinates, and the direction number (as shown above) as parameters.

bool search_grid(const char *word, int x, int y, int direction)

If the current letter matches, depends on the direction, we recursively invoke the same method for the next character in the string with modified coordinates.
If the current letter does not match, the word cannot be found in the given direction starting from the initial coordinates.

Here is the C++ program which implements the basic algorithm for the word match. This is not  a complete program. You may try writing a wrapper which finds the initial coordinates to start the word search (Find the the coordinates where the first letter of the word appears) and do some checks for base cases like empty string etc.

Maximum length of subarray with non-zero elements

Given an array of of size N, How do we find the longest sub-array with all non-zero elements?

For example consider the array {34, 0, 18, 3, 0, 1, 4, 5, 0, 12}, the longest sub-array with non-zero elements is 3 i.e {1,4,5}.

This problem is from Codechef. Follow this link to solve this problem in your own.

The solution is simple. The array contains non zero segments of numbers separated by one or more zeros. While traversing the elements, use two variables current_len, and max_len to track the length of the current segment and maximum segment length seen so far.

Here is the Python implementation of the above. This runs in O(n) time.

Finding the magic index of the array

Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.

For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array[2]. So the output is 2.
If there no such element in the array we can return -1.

Very obvious approach is to do a linear search to find such an element. This will take O(n) in the worst case.

Since the array is sorted, we can modify the binary search to solve this problem more efficiently.

Using binary search we first visit the middle element of the array. 
If array[mid] = mid, simply return mid.
If mid > array[mid], there is no way to find magic index on the left half. Think of an example
[-10, -3, 0, 2, 4, 8]. Here middle index = 3, array[3] = 2.   If we go back from index 3, we can only find elements less than 2 because the array is sorted and it has distinct elements. Hence we can safely skip the left half and proceed to search the right half effectively reducing your search space by half.

In the same way, if mid < array[mid], we can ignore the right half and search only left half of the array.

C++ implementation of the above algorithm is given below.

Finding the minimum and maximum elements in a binary seach tree

Given a binary search tree, how do we find the maximum and minimum elements in it?

For example in the given tree, the maximum element is 8 and the minimum element is 1.
This algorithm is based on the following simple observation.
In a Binary search tree, the minimum element always lies on the left most node and the maximum element always lies on the right most node.
Here is the simple implementation of this algorithm in C++.

Searching for an element in the sorted matrix

Given a row wise and column wise sorted two dimensional array or matrix. How to search for an element efficiently?

Example of the array can be

int[][] matrix = {
                   {1,3,5,7,9},
                   {10,12,14,16,18},
                   {19,21,23,25,27},
                   {28,30,32,34,36},
                   {37,39,41,43,45}
                };

This can be done using the following algorithm. 

We start our search with the top right element. 

  • If it is equal to the key, we print corresponding indices and we are done!. 
  • If the key is greater than the current element, we move to the next row because all the elements in the current row prior to this element are lesser. 
  • If the key is less than the given element, we move to the previous column.  The reason is similar to the above.

We continue this search until we find the key or until we confirm the element is not present. If we reach last row first column, we can confirm that the element is not present.

Here is the java implementation of the above algorithm. The time complexity of this program is O(n) and n is the number of rows and columns.

Finding a number in a sorted array with the least difference from given number

Given a sorted array and a value, we have to find the closest value (with least difference).
For example let the input array be {-2, 4, 7, 11, 17} and the input number is 10, the output should be 11.

This problem is actually a variation of binary search where in we have to find out the closest value found the array. If the given value exists in the array, we have to return that.

A sorted array and binary search gives a hint that we can solve this problem in O( log n) complexity. Here is how we can modify the binary search algorithm to solve this problem.

As in binary search algorithm, we try to search for the given number in the middle of the array. If the element is found, we just return it, because we got the least difference i.e 0.

We also maintain two variables one to store the minimum difference found so far (minDiff), and the other (result) to store the corresponding number. In each iteration, we find the difference between the given value and middle value. If this is lesser than minimum difference, we update the two variables.

At the end of the search we have the required number in the result variable.

Below is the Java code which implements the above algorithm.

Finding the majority element of an array

Given an array of  N elements, the majority element is defined as the one which occurs more than N/2 times.

One simple approach is to find the mode (which appears for most number of times) and check if its frequency is greater than N/2.

Three strategies for finding the mode are discussed in my previous post. The best one among them, the hash map approach takes O(n) time and O(n) space.

We can solve this program even better by using Moore’s voting algorithm. This takes O(n) time and O(1) space.

This algorithm tries to find out the majority number in two iterations. In the first iteration, a probable candidate for majority number is found. In second iteration, we check if the candidate is really the majority number by counting it’s frequency.

The first iteration works as follows. We initialize the first element as the majority number and the count variable is initialized with 1. During further iterations, if the element is equal to majority number, we increment the count, otherwise we decrement the count. If at any point, the count reaches zero, We reassign the majority number to the current element and assign 1 to count.

For example, let us consider the input array {6, 2, 3, 6, 3, 6, 6, 6}. The following table explains the logic.

Iteration# 1 2 3 4 5 6 7 8
Data 6 2 6 6 3 6 1 6
Majority 6 2 6 6 6 6 6 6
count 1 1 1 2 1 2 1 2

At the end 6 is the candidate for majority number. In the second iteration we check the frequency of 6. If it is more than half of the array size it is the majority element.
 
Here is the Java implementation of this approach.

Finding the unique number in an array

Given an array of numbers which contains all the numbers in pairs expect one element. We have to find that unique element.

For example in the array [7,3,8,1,3,4,7,1,8] 4 is the unique element and all the remaining elements occur in pairs.

This is actually a specific case of more generic problem discussed in the my previous post. 

http://comproguide.blogspot.in/2013/06/finding-element-occurring-odd-number-of.html

please refer to the above post for complete solution.