Saddleback search algorithm in Java

Hi coders, this tutorial is focused on Saddleback search algorithm in Java. Many times you have been asked for the searching of an element in various data structures. If we are asked to search an element in a one-dimensional array, we generally go for linear or binary search Algorithm, if we are asked to search an element in a linked list, we use to traverse the linked list. So basically, we have some optimize algorithms to search an element.

Here, suppose if we are asked to search an element in a two-dimensional array such that every row and every column is sorted, then what solutions we are having? The naive approach is to search one by one for the element, but this approach has the time complexity of O(n2).

Example :

Input : matrix[] = {
                    { 1, 3, 5},
                     { 7, 9, 11},
                    { 13, 15, 17}
                  }
element to be searched = 6

Output : Found at index (1, 2).

So here I come up with an optimized algorithm known as Saddleback search algorithm which reduces the time complexity from O(n2) to        O(m + n).

Implementation of the above algorithm

  1. Start checking with the bottom left element of the given two-dimensional array.
  2. If the element matches with the element to be searched then print the index of the element.
  3. If the bottom left element is larger than the element to be searched, then go to the leftmost element of the above row and repeat the second step.
  4. If the bottom left element is smaller than the element to be searched, then move forward in the row till the out of bound does not reach and if out of bound reached, print ” Element not found”.
  5. Repeat the above steps until the element is not found or out of index not reached.

Java code of Saddleback search algorithm

public class SaddleBack
{  
/* The function searchElement will search for the element
,if found it will print the index of the element else will return false 
all will print "Element not found". */
 private static void searchElement(int TwoDiArray[][], int row, int col, int ele) { 
      
    /* set indexes so as to start searching from bottomleft element */
    
    int i = row - 1, j = 0;
    int flag = 0;  
        while (i >= 0 && j < col) 
        { 
            if (TwoDiArray[i][j] == ele) {
                System.out.println("Element found at index: {"+i+", "+j+"}");
                flag = 1;
                 break;
           }
            if (TwoDiArray[i][j] > ele) 
                i--; // moving upward
            else     
                j++; // moving right in the row
        } 
     if(flag == 0) {
          
        System.out.println("Element not found");
}
} 
  
// main function
public static void main(String args[]) { 
 // array declaration and initialization
int TwoDiArray[][] = {{1, 3, 5},
               {7, 9, 11}, 
               {13, 15, 17}}; 
              
searchElement(TwoDiArray, 3, 3, 15); /* passing array, row = 3 , column = 3 and  element = 15*/ 
} 
} 
   
// This code is provided by Anubhav Srivastava 

Hence, the output of the above code will be:

Output:

Element found at index: {2, 1}

You may also learn:

Leave a Reply

Your email address will not be published. Required fields are marked *