binary_search.java

/**
 * Created by xynophon on 15.1.17.
 */
import java.util.Scanner;

public class search {

    public int binary_search_iter(int[] arr, int target){
        int lo = 0;
        int hi = arr.length;
        while(lo < hi){
            int mid = (lo+hi)/2;
            if(arr[mid] == target) return mid;

            if(arr[mid] < target) lo = mid+1;
            else hi = mid;
        }
        return -1;
    }

    public int binary_search_recur(int[] arr, int target, int lo, int hi){
        if(lo >= hi) return -1;

        int mid = (lo+hi)/2;
        if(arr[mid] == target)return mid;

        if(arr[mid] < target)
            return binary_search_recur(arr, target, mid+1, hi);
        else
            return binary_search_recur(arr, target, lo, mid);
    }


    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        sort sr = new sort();

        int[] arr = {19, 18, 20, 10, 1, 5, 2, 4, 3, 6, 8, 7, 9, 11, 13, 15, 12, 16, 17, 14};

        sr.quick_sort(arr, 0, arr.length-1);
        for(int num : arr){
            System.out.print(num+" ");
        }
        System.out.println();
        System.out.print("target : ");
        int target = sc.nextInt();
        search sear = new search();
        System.out.println("index : " + sear.binary_search_iter(arr, target));
//        System.out.println("index : " + sear.binary_search_recur(arr, target, 0, arr.length));
    }
}