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

Pergunta de entrevista da empresa Google

Resposta da entrevista

Empresas seguidas

Buscas de vagas