# Binary Search in Mathematica

Published on 28 April 2022 (Updated: 02 February 2023) Welcome to the Binary Search in Mathematica page! Here, you’ll find the source code for this program as well as a description of how the program works.

## Current Solution

``````(* Code *)

(* Binary search option binarySearch1 uses the built-in, modified to

Needs["Combinatorica`"]

binarySearch1 = If[IntegerQ[#], #, Null] & @*
Combinatorica`BinarySearch;

(* If that is considered cheating, then option binarySearch2 implements it
using 'primitives': *)

binarySearch2 = Function[{l, n},
NestWhile[ (* keep subdividing the search interval *)
Apply[(* convert the single two-element list argument to two arguments *)
Function[{i, j},(* subdivide the given interval into a smaller one containing the item sought *)
Module[{m = Floor[(i + j)/2], me},(* use some definite element as the midpoint to test *)
me = l[[m]];
Which[
(* Did we find the element we're searching for? *)
me == n, m,
(* Element is before the midpoint?  Then either keep searching, or give up *)
n < me, If[i < m, {i, m - 1}, Null],
(* Element is after the midpoint?  Then either keep searching, or give up *)
n > me, If[m < j, {m + 1, j}, Null]]]]],
{1, Length[l]} (* begin by considering the entire list to search within *),
ListQ (* while we are still searching *)]];

(* The outer function does the string parsing: *)

binarySearchMain = Function[{l, i},
Module[{e = "Usage: please provide a list of sorted integers (\"1, 4, 5, 11, 12\") and the integer to find (\"11\")"},
Catch[
If[
(* convert position to "true" or Null to "false" *)
IntegerQ[binarySearch2 @@ Map[
(* convert string to integer, or throw *)
s \[Function] If[StringMatchQ[s, DigitCharacter ..],
FromDigits[s],
Throw[e]],
(* construct two arguments to binary search: list of search array, item to search; as strings *)
{StringSplit[If[StringLength[l] > 0, l, Throw[e]], ", "], i},
{-1} (* at each leaf *)]],
"true", "false"]]]];

(* Valid Tests *)
Print /@ Apply[binarySearchMain] /@ {
{"1, 4, 5, 11, 12", "4"},
{"1, 3, 5, 7", "1"},
{"1, 3, 5, 7", "7"},
{"5", "5"},
{"5", "7"},
{"1, 3, 5, 6", "7"}};

(* Invalid Tests *)
binarySearchMain["1, 2, 3, 4",""]
binarySearchMain["", "5"]

(* Not checking the 'list is unsorted' invalid test. *)
``````

Binary Search in Mathematica was written by:

• Ben Hekster

If you see anything you’d like to change or update, please consider contributing.

## How to Implement the Solution

No ‘How to Implement the Solution’ section available. Please consider contributing.

## How to Run the Solution

No ‘How to Run the Solution’ section available. Please consider contributing.