Logic Building: Binary Search on sorted List in Apex

For instance, you’re searching for a person in the phone book Their name starts with S. You could start at the beginning and keep flipping pages until you get to the S. But you’re more likely to start at a page in the middle, because you know the Ks are going to be near the middle of the phone book.

This is a search problem. Binary search is an algorithm; its input is a sorted list of elements. If an element you’re looking for is in that list, binary search returns the position where it’s located.

Binary search is implemented using following steps…

Step 1 – Read the search element from the user.
Step 2 – Find the middle element in the sorted list.
Step 3 – Compare the search element with the middle element in the sorted list.
Step 4 – If both are matched, then display “Given element is found!!!” and terminate the function.
Step 5 – If both are not matched, then check whether the search element is smaller or larger than the middle element.
Step 6 – If the search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for the left sublist of the middle element.
Step 7 – If the search element is larger than middle element, repeat steps 2, 3, 4 and 5 for the right sublist of the middle element.
Step 8 – Repeat the same process until we find the search element in the list or until sublist contains only one element.
Step 9 – If that element also doesn’t match with the search element, then display “Element is not found in the list!!!” and terminate the function.

Example: From the sorted list, search 40 in the list

Pseudocode

Procedure binary_search
   A ← sorted list
   n ← size of list
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

BinarySearchExample.apxc

Public class BinarySearchExample{  
 public static void binarySearch(list<integer> numval, integer first, integer last, integer key){  
  // calculate middle of the array. To do so, take the left and rightmost values of the index and divide them by 2. 
     integer mid = (first + last)/2;
   while( first <= last ){ 
   //Now we compare the value stored at middle of list, with the value being searched
      if ( numval[mid] < key ){   
        first = mid + 1;    
      }else if (numval[mid] == key){  
        System.debug('Element is found at index: ' +  mid);  
        break;  
      }else{  
         last = mid - 1;  
      }  
      mid = (first + last)/2;  
   }  
   if ( first > last ){  
      System.debug('Element is not found!');  
   }  
 }
}

Anonymous Window

 list<integer> numval = new list<integer>{10,20,30,40,50};  
        integer key = 40;  
        integer last=numval.size() - 1;  
        BinarySearchExample.binarySearch(numval,0,last,key);

Output