<aside> 📌 linear search: go through an array each element one at a time to find what you need

</aside>

• based on the index of the element, linear search can be inefficient
• chances are when you get a set of data, it will be unsorted

in a sorted array (looking for 32)

<aside> 🔒 3 8 9 10 12 15 32 35 36 48

</aside>

• divide the length of the array by 2 to get the "middle element"

  • in this case, it is 12, at index 4

• compare the number you are looking for to the "middle element"

  • is 32 greater than 1? yes, so lets go to the right side of the array
  • set new array from middle element + 1 to the end of the array

  <aside> 🔒 15 32 35 36 48

  </aside>

• find the middle element, which is 35. is 35 greater than 32?

  • no, so let's cut our array in half again

  <aside> 🔒 15 32

  </aside>

//sample code

public static int binarySearch(int[]arr, int key){ 
        //where key is the number we want to search for

        int bottom = 0; //lowest index
        int index = -1;
        int top = arr.length-1; //
        int middle;

        while(bottom<=top){
            middle = bottom + ((top-bottom)/2); //middle index

            if(arr[middle]>key){ //if the key is in the lower half 
                top = middle - 1;
            }
            else if(arr[middle]<key){ //if the key is in the upper half 
                bottom = middle + 1;
            }

            else if(arr[middle] == key){ //if the middle index is the key
                index = middle;
                return index;
            }

            comparisons ++;
    
        }
        
	return index;  //if the element is not in the array

}