(Note:

Your teachers must have told you this about searching in an array: If you have a sorted array, then one of the most efficient way to find position of any element in that array is binary search.

I say: Fine, then why not just convert that array to a Red-Black Tree ? I find Red-Black Tree as a better option, as in binary search, you have to calculate the midpoint in every iteration/recursive-call during search.

Before you see the code, I must add: if the size of your array is

The code written above, is only to get you started. An actual application where you may have to write a similar code can be different, and you have to adjust parts of this code to suit your requirement. Here is one such example:

There are 2 arrays. One array contains phone/mobile numbers, and the other array contains names of owners of each number. eg: if

This is where the concept of

*Red-Black Tree*is a*Balanced Binary Search Tree*)Your teachers must have told you this about searching in an array: If you have a sorted array, then one of the most efficient way to find position of any element in that array is binary search.

I say: Fine, then why not just convert that array to a Red-Black Tree ? I find Red-Black Tree as a better option, as in binary search, you have to calculate the midpoint in every iteration/recursive-call during search.

Before you see the code, I must add: if the size of your array is

*N*, then this code will generate*N*number of objects of__Node__class. Add to that, in each of these objects there are going to be 4 variables of 32bits each [Or on a 64 bit machine: 2 variables of 32 bit (the 2 integers) & 2 variables of 64 bit (the 2 object references)]./* * Programming language: Java */ class RedBlackTree { static class Node { int key; int value; Node left; Node right; Node(int key,int value) { this.key = key; this.value = value; } } Node root; public RedBlackTree(int[]sorted_integers) { root = arrayToRedBlackTreeRoot(sorted_integers,0,sorted_integers.length-1); }static Node arrayToRedBlackTreeRoot(int[]integers,int i,int j) { if(i>j) return null; int x=(j+i)/2; Node local_root=new Node(integers[x],x); if(i<j) { local_root.left = arrayToRedBlackTreeRoot(integers,i,x-1); local_root.right = arrayToRedBlackTreeRoot(integers,x+1,j); } return local_root; }}

The code written above, is only to get you started. An actual application where you may have to write a similar code can be different, and you have to adjust parts of this code to suit your requirement. Here is one such example:

There are 2 arrays. One array contains phone/mobile numbers, and the other array contains names of owners of each number. eg: if

*number[4]=9876543210*and*name[4]="John Ray"*, then John Ray's number is 9876543210. You are asked to write a program that finds the name of the person when you have that person's number. For that first make following changes/additions in the above code:- Change type of
*integers*and*sorted_array*to*long[]* - Change type of
*key*to*long* - Add a function named
*find*in the class*RedBlackTree* - Write the folllowing in your main() function:

/* * Programming language: Java */ public int find(long key) { Node node=root; while(node!=null) { if(node.key==key) return node.value; else if(node.key<key) node=node.right; else if(node.key>key) node=node.left; } return -1; }

/* * Programming Language: Java */ long[]numbers=new long[10]; String[]names=new String[10]; // Home Work: Write code to initialize both arrays from any input. // bubble sort starts here: (you can choose your favourite algorithm) for(int i=0 ; i<numbers.length ; ++i) for(int j=1,n=numbers.length-i; j<n ; ++j ) if(numbers[j-1]>numbers[j]) { long temp_number=numbers[j-1]; numbers[j-1]=numbers[j]; numbers[j]=temp_number; String temp_name=names[j-1]; names[j-1]=names[j]; names[j]=temp_name; } RedBlackTree tree=new RedBlackTree(numbers); long number_x = 9876543210L;// Home Work: Read this number from input. int found=tree.find(number_x); System.out.println("The number: "+number_x+", belongs to "+(found==-1?"nobody":names[found]));Though the above written code can work to give you a fair result, this may not be the most efficient way to write a program.

This is where the concept of

**comes in. In C++, STL has***MAP**map.h*for it. In Java programming language an implementation of*java.util.Map*will do. But what change in above code will do it for us? The answer is: Instead of puting index of names in value, put the name itself as value. Thats it! So finally, we have a code that looks like this:/** * Programming Language: Java * @author Abhishek */ class RedBlackTree { static class Node { long key; String value; Node left; Node right; Node(long key, String value) { this.key = key; this.value = value; } } Node root; public RedBlackTree(long[] numbers,String[]names) { root = arrayToRedBlackTreeRoot(names,numbers, 0, numbers.length - 1); } static Node arrayToRedBlackTreeRoot(String[]names,long[] numbers, int i, int j) { if (i > j) { return null; } int x = (j + i) / 2; Node local_root = new Node(numbers[x], names[x]); if (i < j) { local_root.left = arrayToRedBlackTreeRoot(names,numbers, i, x - 1); local_root.right = arrayToRedBlackTreeRoot(names,numbers, x + 1, j); } return local_root; } public String find(long key) { Node node = root; while (node != null) { if (node.key == key) { return node.value; } else if (node.key < key) { node = node.right; } else if (node.key > key) { node = node.left; } } return "nobody"; } } public class NameNumber { /** * @param args the command line arguments */ public static void main(String[] args) { long[] numbers = new long[10]; String[] names = new String[10]; // Home Work: Write code to initialize both arrays from any input.(file/console) // bubble sort starts here: (you can choose your favourite algorithm) for (int i = 0; i < numbers.length; ++i) { for (int j = 1, n = numbers.length - i; j < n; ++j) { if (numbers[j - 1] > numbers[j]) { long temp_number = numbers[j - 1]; numbers[j - 1] = numbers[j]; numbers[j] = temp_number; String temp_name = names[j - 1]; names[j - 1] = names[j]; names[j] = temp_name; } } } RedBlackTree tree = new RedBlackTree(numbers,names); long number_x = 9876543210L;// Home Work: Read this number from input. System.out.println("The number: " + number_x + ", belongs to " + tree.find(number_x)); } }You can also replace the statement

*return "nobody"*with*return null*in the code above. Also try thinking of some programming cases where a number-to-object map can be replaced with this code. Like: where you may have used*java.util.HashMap<Long,String>*(in Java).