explain binary search, running time, when is it advantageous

Question

Liron · Accepted Answer

package com.google;

public class BinarySearch {

	public static int binSer(int i, int j, int num, int[] arr){
	    if (i > j){
	        return -1;
	    }
	    int mid = (i+j)/2;
	    if (arr[mid] == num){
	        return mid;
	    }
	    if (arr[mid] < num){
	        return binSer(mid+1,j,num,arr);
	    }
	    else {
	        return binSer(i,mid,num,arr);
	    }
	}
	
	public static void main(String[] args){
		int[] arr = {1,2,3,5,6,8,9};
		System.out.println(binSer(0, arr.length-1, 9, arr));
	}
}


Binary search is usually used to find an element in a sorted array in logn time. When the array is not sorted we cannot use it to find an element, but what we can do is partition from quick sort and then continue on the part which has the element. this will take O(n) time.

Google

Google interview question

Interview Answer

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches