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;
     }
}

No comments:

Post a Comment