Binary Search and Insert

submited by

Style Pass

2023-05-26 06:00:02

When dealing with arrays it’s often necessary to keep their elements in sorted order. The easiest way is to use an insert algorithm that always puts element into the array in sorted order. That said, you don’t know where elements will end up in the array because if you already knew the order you wouldn’t need to sort in the first place. At some point you will need to pull elements back out and you will want a quick way to find a given element.

Binary search and insert are great all around algorithms that do both of these. It’s a simple divide and conquer approach that is conceptually vey simple. The array is divided into two parts and the search value is compared to to each part. One side is selected based on greater or less than. Then the side is divided and the comparison takes place again. This happens until the value is found or there are two values one above and one below (for insert).

While this is part of C89 and should be always be available it’s good to know how it works. There is the off chance that you want to use a language that doesn’t have a built in binary search function.