Very important concept "The Binary Search" by Keshav

This code is implemented and provided by Keshav from Cetpa Infotech.

Binary Search : search an element [ stbs==>String to be search ] over
sorted array of n-elements by repeatedly dividing the search interval in half.
If 'stbs' is found in the array, return the position of element in the array
else return -1.
step 1: initially compare the 'stbs' begin with an interval covering 
the whole array.
if there is only one element in the array, then compare 'stbs' with
element. if it matches, then return 0 as index value. else return -1.
step 2: find the mid element. and compare it with 'stbs'. if matches, return 
mid position 
step 3: else if compareTo() method return -ve value then 'stbs' 
can be match in left half subarray before the mid element.
step 4: else 'stbs' can be match in right half subarray after the mid element.
  
NOTE: 1.Please create a Java project in Eclipse and save this class as 
BinarySearchForString.java
   2.Binary search only works on sorted array.
       Click here to know more about binary search


import java.util.*;
class BinarySearchForString
{
/* lets define a method search() which will be call recursively, this method will
take four arguments, 1st is an array of String, 2nd and 3rd argument will define
an interval and 4th argument will be 'String to be search' [stbs].
*/
static int search(String data[],int i,int j,String stbs)
{
// if (i==j) that means there is only one element in array.
if(i==j){
// lets compare the stbs with array element by calling compareTo()
// method, if match then return the position of element.
if(stbs.compareTo(data[i])==0){
return i;
}
// else return -1. ==> it means element is not present in array.
else{
return -1;
}
}
// if there is more then one element then find the mid position and then
// compare the stbs with mid position element.
else{
// so lets get the mid position.
int mid=(i+j)/2;
/* lets compare the stbs with mid position element.
if matches [means, if compareTo() method return 0 then ]
return mid position.*/
if(stbs.compareTo(data[mid])==0){
return mid;
}
/* if compareTo() method return negative (-ve) value, then 'stbs'
can be match in left half subarray before the mid element i.e.
[ from i to mid-1 ] */
else if(stbs.compareTo(data[mid])<0){
return search(data,i,mid-1,stbs);
}
// else 'stbs' can be match in right half subarray
// after the mid element i.e. [ from mid+1 to j ]
else{
return search(data,mid+1,j,stbs);
}
}
}


public static void main(String[] args)
{
// lets define an array of String
String str[]={"calcutta","delhi","hyderaba","jaipur","mumbai","pune"};
// lets get the number of element in the array.
int n=str.length;

Scanner sc=new Scanner(System.in);
System.out.println();
// now here i am going to show the element present in the array.
for(String s:str)
{
System.out.print(s+"  ");
}

System.out.println("\n");
System.out.print("enter String that to be search:");
String stbs=sc.next();
/* lets call the search() method to find the position of 'stbs'.
this method will return the postion of 'stbs' available inside
the array. else return -1. */
int index=search(str,0,n-1,stbs);
if(index!=-1){
System.out.println("the String is at index: "+index);
}
else{
System.out.println("the String is not availble: "+index);
}
}
}


now lets calculate the Time Complexity.
assume, there is n element in the array. and T(n) be the amount of time required to
find the element [stbs] using above algorithm.

but before this, let analysis the code.
1. if(i==j){
2. if(stbs.compareTo(data[i])==0){
3. return i;
4. }
5. else{
6. return -1;
7. }

from line number 1 to 7, there is one comparison which is done in O(1) time.

8. else{
9. int mid=(i+j)/2; ==> here is 0 comparison ==>mid position can
find in constant time that is O(1) time.

10. if(stbs.compareTo(data[mid])==0){
11.  return mid; ==> here is only one comparision ==>O(1) time.
12. }
13. else if(stbs.compareTo(data[mid])<0)
                        { ==> here is also one comparison
==> that can be done in O(1) time.
14. return search(data,i,mid-1,stbs);==> it takes T(n/2) time.
15. }
16. else{
17. return search(data,mid+1,j,stbs);==> it takes T(n/2) time.
18. }
19. }

overall time is 

T(n) = O(1) ==> if n=1 <== this is best case
(or)
O(1)+O(1)+O(1)+T(n/2) <== this is worst case

so in the worst case, time complexity is  
T(n) = T(n/2)+c, here c means constant time which is used to represent
         [O(1)+O(1)+O(1)]
         after solving this by using substitution approach , 
         we get Time Complexity as O(log n).