Given a sorted array, find k in least possible time in Java

Given a sorted array and a value k, write a program to find whether that number is present in that array or not.

The first solution that comes to the mind for this problem is to traverse through the entire array and find whether it is having the value k and return true or false. This takes O(n) running time. But then, we are presented with a hint that the input array is sorted (lets assume in ascending order). This problem can be attacked by doing a divide and rule analysis.

This can be done recursively. See whether k is inbetween the last and first element in the array. If it is, then divide the array into two and repeat the same. If its not, simply return false. Yes, its as simple as that. Following is the java code for the same.

Leave some comments if you have anything to say.

Cheers!
Braga

Find three numbers in an array which forms a maximum product

This problem again is asked as a coding question in one of the top companies. I have provided the solution for this in C++.

Question: 
Given an array of integers (unsigned integers > 0), find three numbers in that array which form the maximum product. [O(nlogn), O(n) solutions are available ].
int[] MaxProduct(int[] input, int size)

Solution:
The program expects both the solutions, one in O(n) time and the other one in O(nlogn). To achieve O(nlogn), sort the entire set by using quick sort or merge sort and take the top three values.
I have provided the code for the O(n) case. It does a single scan on the entire set of elements once and finds the largest three numbers with the logic as shown below.

//============================================================================
// Name        : three_largest_elems.cpp
// Author      : Prabhu Jayaraman (My honorable room mate, college mate, work colleague)
// Version     : v1
// Copyright   : open
// Description : To find three largest numbers in an array in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main()
{
 int a[10] = {1,2,33,4,15,6,7,28,9,10};
 int largest_1 = 0, largest_2 = 0, largest_3 = 0;

 for(int i=0;i<10;i++)
 {
  if(a[i] > largest_3 && a[i] < largest_2)
  {
   largest_3 = a[i];
  }
  else if(a[i] > largest_2 && a[i] < largest_1)
  {
   largest_3 = largest_2;
   largest_2 = a[i];
  }
  else if(a[i] > largest_1)
  {
   largest_3 = largest_2;
   largest_2 = largest_1;
   largest_1 = a[i];
  }
 }
 cout << "largest :" << largest_1 << endl;
 cout << "2nd largest :" << largest_2 << endl;
 cout << "3rd largest :" << largest_3 << endl;
 return 0;
}

Cheers!!
Bragaadeesh

Searching in a Binary Search Tree in Java

Now that we have a working version of a binary search tree fully implemented in Java, lets go a step ahead and start analyzing that piece of code.

Binary search tree is a data structure which has the following public methods exposed

public void add(int data);
public boolean search(int searchData);
public void printOrdered();

Ofcourse, the above three methods are not the only methods present in a binary search tree, but once these methods are understood and analyzed, understanding the rest of the binary tree should not be a big problem.

Adding elements to a binary tree : In the example program that I've written, I am using only integers as the node data to hold values and ofcourse you need something that is comparable to make binary search trees realistic (refer my previous post on comparable objects). While adding data to a binary search tree, we need to follow the simple rule - lesser should go left and greater then or equal should go to the right of the parent node. By taking a snap at the code, the add(int data) method internally calls a private method that does the job in recursion.

Searching elements in a tree : Searching elements in any data structure is a essential part that reflects the space and time complexity and Binary search tree is no exception. To search from a balanced binary search tree, it would take only O(logn) whereas the same is not so in case of an Array. The simple reason being, for arrays, we need to traverse the entire array sequentially in which the worst case would produce O(n). Consider the below example where in we need to search the element 5.

Whereas in a binary search, the depth count would simply provide the desired result.
Consider a situation in a balanced binary search tree of 7 elements, when the value given to search is at its leaf (which would be the worst case here). The example shown below is a balanced and a perfect binary search tree (which we would look into future posts). Assume the element we need to find is 5. First inspect the root (4), our value is greater, so go the right node, then inspect it (6), our value is lesser so go the left node, bingo! we found our result. This took only 2 comparisons of a tree of depth 2 whereas it look 7 comparisons in an array of length 7! Through this we can come to conclusion that binary trees perform search in O(logn) time.

The method printOrdered() is something we have to allocate time and look into a different post. As for now, lets convince ourselves that binary tree's search is powerful enough to perform the search operation in O(logn) time.
Rest, later. Cheers,
Bragaadeesh.

Bubble Sort in Java

Bubble sort is the most simplest form of sorts available. In real lives, the bubbles formed under water tend to come up to the surface. Larger the bubble, faster it will come up. Same way in this sorting technique, we would try to push the larger value up in case of descending or vice versa.

Pros:
1. Simple to implement.
2. Very easy to understand.

Cons:
1. Runs in O(n²) complexity.
2. Severe performance issues if the sample size increases.

The java code for this sorting technique is as follows,

package dsa.sorting;

public class BubbleSort {

 public static int SIZE = 100000;

 public static void main(String args[]) {
  int[] a = new int[SIZE];
  for (int i = 0; i < SIZE; i++) {
   a[i] = (int) (Math.random() * SIZE);
  }
  long start = System.currentTimeMillis();
  BubbleSort mNew = new BubbleSort();
  mNew.sort(a);
  long end = System.currentTimeMillis();
  System.out.println("Time taken to sort a 100000 elements : "
    + (end - start) + " milliseconds");
 }

 public int[] sort(int[] input) {
  int temp;
  for (int i = 0; i < input.length; i++) {
   for (int j = i; j < input.length; j++) {
    if (input[i] > input[j]) {
     temp = input[i];
     input[i] = input[j];
     input[j] = temp;
    }
   }
  }
  return input;
 }
}
// Time taken to sort a 100000 elements : 28554 milliseconds

You may see from the above example that it takes insanely higher time for sorting only a hundred thousand elements. 29 seconds is a very poor outcome. We will look into O(nlogn) sort types on why and how it reduces this running time.

Cheers,
Bragaadeesh.