## Binary Search

public static int binarySearch(int[]array,int key){ //looks for the index of the element that has value key, returns index. array must be sorted

int min=0; //initializes min, max, guess

int max=array.length-1;

int guess=(min+max)/2;

while(array[guess]!=key){ //keeps on looking until key is found

if(min==guess||max==guess){//if min=guess, max=guess, the key does not exist in the array

return(-1);//returns -1 if key is not found

}

if(array[guess]>key){//you only have to search between min and guess

max=guess;

}

else{//search between max and guess

min=guess;

}

guess=(min+max)/2;//new value for guess-middle of the interval

}

return(guess);//exists the loop of key is found-returns the index

}

Binary Search is an algorithm that finds the index of a certain key inside a sorted array. The java implementation above is above a "linear" searching algorithm that requires O(N) times, this requires O(log(n)). The algorithm looks at the middle of the array. If the value is too low, it must be in the top half of the array; if the value is too high, it must be in the bottom half of the array. This is repeated with the smaller parts, so the searching area is split in half until the value is found. If max=guess or min=guess, that means the searching area is between two numbers, but neither gives the right key, so key doesn't exist inside the array, and -1 is returned. Otherwise, the index is returned.

int min=0; //initializes min, max, guess

int max=array.length-1;

int guess=(min+max)/2;

while(array[guess]!=key){ //keeps on looking until key is found

if(min==guess||max==guess){//if min=guess, max=guess, the key does not exist in the array

return(-1);//returns -1 if key is not found

}

if(array[guess]>key){//you only have to search between min and guess

max=guess;

}

else{//search between max and guess

min=guess;

}

guess=(min+max)/2;//new value for guess-middle of the interval

}

return(guess);//exists the loop of key is found-returns the index

}

Binary Search is an algorithm that finds the index of a certain key inside a sorted array. The java implementation above is above a "linear" searching algorithm that requires O(N) times, this requires O(log(n)). The algorithm looks at the middle of the array. If the value is too low, it must be in the top half of the array; if the value is too high, it must be in the bottom half of the array. This is repeated with the smaller parts, so the searching area is split in half until the value is found. If max=guess or min=guess, that means the searching area is between two numbers, but neither gives the right key, so key doesn't exist inside the array, and -1 is returned. Otherwise, the index is returned.

Provided by website-hit-counters.com site. |