Pages

▼

Sunday, July 19, 2015

Binary Search

Array must be sorted first before searching.

example
Sorted array: L = [1, 3, 4, 6, 8, 9, 11]
   Target value: X = 4
   Compare X to 6. X is smaller. Repeat with L = [1, 3, 4].
   Compare X to 3. X is larger. Repeat with L = [4].
   Compare X to 4. X equals 4, so the position is returned.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class BinarySearch{

     public static void main(String []args){
        // Binary search must be sort first
        int[] array = new int[]{10,20,50,53,68,81,92,105,110,200,280,360,361,386,400};
        
        if(binSearch(array,81) == -1)
            System.out.print("not found");
        else
            System.out.print("found at index "+ binSearch(array,81));
     }
     
     public static int binSearch(int[] arr, int search){
         int first =0;
         int last = arr.length-1;
         int mid=0;
         
         while(first<=last){
             mid = (first+last)/2;
             
             if(arr[mid] == search)
                return mid;
             else if (arr[mid]<search)
                first = mid+1;
             else
                last = mid-1;
         }
         
         return -1;
     }
}
at No comments:

Monday, July 13, 2015

Longest Palindrome in String

Longest Palindromic substring. Given a string, find the longest substring which is palindrome. For example, if the given string is "forgeeksskeegfor", the output should be "geeksskeeg".

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class PalinLong{

     public static void main(String []args){
        
        String s = "forgeeksskeegfor";
        String longest="";
        for(int x=0;x<s.length();x++){
            for(int y=x+1;y<=s.length();y++){
                String t = s.substring(x,y);
                if(isPalin(t)){
                    if(t.length()>longest.length()){
                        longest = t;
                    }
                }
            }   
        }
        
        System.out.print(longest);
     }
     
     public static boolean isPalin(String s){
         String rev="";
         
         for(int x=s.length()-1;x>=0;x--){
             rev = rev + s.charAt(x);
         }
         
        if(rev.equals(s))
            return true;
        else
            return false;
     }
}
at No comments: