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.