Dichotomous search algorithm

Dichotomous search is significantly faster than linear search, which is to compare with items in a list sequentially unless the list is very short or if the item sought is at the top of the list, which is usually not predictable.

This algorithm runs on an ordered set and uses the order to control the search. The word dichotomy comes from the Greek διχοτόμηση which means: cut in half.

C++ provides binary_search functionality in the STL library.
The NET Framework has similar functions in basic libraries (System.Array).
The general code below should not cause problems in other programming languages.

Algorithm principle

How to quickly find the word Untel in the dictionary? We open the book in the middle and fall on words starting with m, letters that are in the center of the dictionary. It can be seen that untel cannot be in the first half, so we limit the search to the second, which goes from m to z.
Therefore, we postpone the first half and make the same reasoning about the second and so on for each new part, we gradually reduce the list, moving to either the left or right side, so that we inevitably get to the page containing the desired word.

The dichotomous principle of search can be generalized to any type of problem, since the objects of the search field can form a sequence and a comparison of the order in the sequence can be made.

It is easy to implement an algorithm on a computer due to recursiveness, but it can also be implemented iteratively.

Recursive version

Base code (scriptol):

array A = []

int binarySearch(int value, int starting, int ending)
  if ending < starting return -1
  int mid = (starting + ending)  / 2	
  if A[mid]
      = value :     return mid
      > value :     ending = mid - 1
      < value :     starting = mid + 1   
  /if	 
return  binarySearch(value, starting, ending)

Table A is viewed as a global variable, which greatly speeds up the execution of the script, and the launch index and ending variables are used to select a gradually reduced fragment of the array.

Apply to a text table

Algorithm code:

int binarySearch(text value, int starting, int ending)
  if ending < starting return -1
  int mid = (starting + ending)  / 2
  int result = strcmp(value, A[mid])  	

  if result
  = 0 :  return mid
  < 0 :  ending = mid - 1
  > 0 :  starting = mid + 1   
  /if
return  binarySearch(value, starting, ending)

Only the comparison function has changed. The strcmp function returns 0 when the strings are identical, a number less than 0 if the first is classified to the second, and greater than 0 if not.

Iterative version

Base code (scriptol):

int binarySearch(int value, array A)
  int starting = 0
  int ending = A.size() 
  int mid
  int length
  
  while forever  
      if starting > ending return -1   
      length = ending - starting 

      if length = 0
          if value = A[starting] return starting
          return -1 
       /if	 
      mid = starting + int(length / 2)

      if value 
          < A[mid] : ending = mid - 1
          > A[mid] : starting = mid + 1
      else
           return mid
      /if
  /while
return -1

The example uses an array as a function parameter, but it can also be used as a global variable, as can a recursive algorithm.