Binary Search in Golang

binarysearch.go

package main

import "fmt"

func main() {

	smallarray := []int{1, 4, 5, 5, 7, 9, 10, 12, 13, 15, 16, 17, 19, 22, 23, 27, 30, 32, 36, 39, 42, 44, 45, 46, 47, 50}

	bigarray := []int{
		1, 2, 3, 5, 6, 7, 8, 10, 11, 14, 15, 16, 18, 19, 21, 24, 25, 29, 30, 31, 32, 33, 35,
		37, 40, 41, 42, 46, 48, 51, 52, 53, 55, 57, 62, 63, 65, 66, 68, 70, 71, 75, 76, 77, 79,
		80, 83, 84, 85, 86, 90, 92, 97, 98, 99, 100, 101, 102, 104, 105, 107, 109, 110, 111, 113,
		114, 116, 117, 120, 121, 122, 123, 125, 126, 127, 129, 131, 134, 136, 137, 138, 139, 140,
		141, 142, 143, 144, 146, 150, 151, 154, 155, 157, 158, 159, 162, 163, 164, 165, 166, 167,
		169, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 188, 189,
		190, 191, 192, 193, 194, 195, 197, 199, 200, 201, 202, 204, 205, 206, 207, 208, 211, 214,
		216, 218, 219, 221, 222, 223, 224, 225, 226, 227, 229, 230, 231, 233, 235, 237, 239, 240,
		244, 245, 247, 249, 250, 252, 254, 255, 257, 258, 260, 261, 262, 263, 264, 266, 267, 268,
		269, 270, 271, 273, 274, 276, 277, 278, 279, 282, 283, 284, 288, 290, 291, 292, 293, 294,
		295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 307, 308, 310, 311, 312, 314, 315,
		316, 317, 318, 320, 321, 322, 323, 324, 327, 329, 330, 332, 334, 335, 336, 337, 338, 340,
		344, 345, 348, 349, 351, 353, 355, 356, 358, 359, 360, 363, 364, 365, 367, 370, 371, 372,
		373, 374, 375, 376, 377, 378, 380, 381, 382, 384, 387, 388, 392, 393, 394, 398, 400, 401,
		402, 403, 405, 406, 408, 410, 412, 414, 415, 417, 418, 419, 420, 421, 422, 423, 424, 425,
		426, 429, 431, 432, 433, 437, 438, 439, 443, 445, 446, 447, 450, 451, 456, 458, 460, 461,
		463, 464, 465, 467, 470, 471, 472, 473, 474, 475, 478, 479, 480, 481, 483, 484, 485, 486,
		488, 489, 492, 493, 495, 496, 497, 498, 499, 500, 501, 502, 504, 506, 507, 509, 511, 515,
		516, 517, 518, 519, 520, 521, 522, 523, 526, 531, 533, 534, 535, 541, 542, 543, 544, 545,
		546, 549, 550, 551, 553, 554, 555, 561, 562, 563, 564, 565, 571, 572, 574, 575, 577, 578,
		579, 581, 583, 584, 586, 591, 592, 594, 596, 597, 599, 600, 603, 604, 605, 606, 608, 609,
		610, 612, 614, 615, 616, 618, 621, 623, 624, 625, 626, 627, 629, 630, 632, 635, 638, 639,
		640, 641, 643, 644, 645, 646, 648, 649, 651, 654, 655, 656, 658, 660, 664, 665, 667, 670,
		671, 672, 673, 675, 677, 679, 680, 681, 682, 684, 685, 688, 689, 690, 691, 693, 697, 700,
		702, 703, 705, 706, 707, 708, 709, 710, 712, 714, 719, 720, 721, 723, 725, 728, 730, 731,
		732, 734, 738, 739, 742, 743, 744, 745, 746, 748, 749, 750, 753, 754, 755, 757, 759, 761,
		762, 763, 764, 765, 768, 769, 770, 771, 772, 773, 774, 775, 776, 778, 779, 780, 781, 785,
		787, 788, 789, 790, 791, 793, 794, 795, 796, 797, 798, 799, 800, 802, 803, 804, 805, 807,
		809, 811, 813, 814, 815, 816, 818, 819, 820, 821, 822, 823, 824, 826, 828, 829, 830, 831,
		835, 839, 840, 841, 843, 845, 846, 848, 853, 854, 855, 856, 857, 858, 859, 860, 861, 862,
		863, 865, 866, 868, 869, 870, 873, 875, 876, 878, 881, 882, 883, 886, 889, 893, 894, 895,
		898, 899, 900, 901, 902, 903, 904, 905, 909, 910, 912, 913, 914, 915, 916, 917, 918, 919,
		921, 922, 924, 926, 927, 930, 932, 933, 935, 938, 939, 940, 942, 948, 949, 951, 952, 954,
		956, 960, 962, 963, 964, 965, 966, 968, 969, 970, 971, 974, 976, 978, 979, 980, 982, 984,
		985, 986, 987, 988, 991, 992, 995, 996, 997, 998, 1002, 1003, 1004, 1005, 1008, 1010, 1011,
		1016, 1017, 1018, 1019, 1020, 1021, 1023, 1024, 1028, 1031, 1032, 1033, 1034, 1035, 1037,
		1039, 1041, 1042, 1043, 1046, 1047, 1048, 1049, 1051, 1052, 1053, 1054, 1055, 1059, 1060,
		1063, 1065, 1067, 1069, 1070, 1071, 1072, 1073, 1074, 1077, 1079, 1080, 1081, 1082, 1084,
		1085, 1087, 1091, 1093, 1096, 1099, 1100, 1101, 1102, 1104, 1105, 1107, 1108, 1111, 1112,
		1116, 1117, 1120, 1122, 1123, 1124, 1125, 1126, 1127, 1128, 1131, 1132, 1136, 1138, 1140,
		1141, 1142, 1143, 1144, 1145, 1146, 1147, 1148, 1149, 1150, 1152, 1153, 1154, 1155, 1159,
		1160, 1161, 1162, 1164, 1165, 1167, 1168, 1174, 1176, 1178, 1180, 1181, 1182, 1184, 1186,
		1188, 1189, 1190, 1191, 1193, 1195, 1197, 1198, 1200, 1201, 1202, 1204, 1205, 1206, 1207,
		1211, 1216, 1218, 1219, 1220, 1221, 1223, 1224, 1225, 1226, 1227, 1231, 1232, 1233, 1234,
		1237, 1238, 1239, 1240, 1241, 1243, 1244, 1246, 1247, 1248, 1249, 1251, 1253, 1254, 1256,
		1257, 1258, 1259, 1260, 1261, 1263, 1264, 1265, 1266, 1267, 1269, 1270, 1271, 1274, 1275,
		1276, 1280, 1281, 1282, 1283, 1284, 1285, 1286, 1287, 1288, 1289, 1290, 1294, 1295, 1297,
		1301, 1302, 1303, 1304, 1305, 1306, 1308, 1311, 1313, 1314, 1315, 1318, 1320, 1321, 1323,
		1324, 1326, 1327, 1330, 1332, 1333, 1334, 1335, 1337, 1338, 1339, 1340, 1341, 1342, 1343,
		1345, 1347, 1348, 1349, 1350, 1352, 1355, 1358, 1359, 1360, 1362, 1363, 1364, 1368, 1370,
		1371, 1372, 1373, 1374, 1375, 1378, 1381, 1382, 1385, 1387, 1388, 1390, 1391, 1394, 1396,
		1397, 1398, 1400, 1401, 1402, 1403, 1404, 1405, 1406, 1410, 1411, 1412, 1415, 1416, 1417,
		1419, 1420, 1421, 1422, 1424, 1425, 1426, 1427, 1428, 1429, 1430, 1431, 1433, 1435, 1437,
		1438, 1439, 1440, 1441, 1442, 1443, 1444, 1445, 1448, 1450, 1451, 1452, 1453, 1458, 1462,
		1466, 1467, 1468, 1469, 1470, 1471, 1472, 1473, 1474, 1475, 1476, 1477, 1478, 1479, 1480,
		1481, 1482, 1484, 1485, 1486, 1487, 1490, 1491, 1492, 1493, 1494, 1495, 1497, 1499, 1502,
		1506, 1507, 1513, 1514, 1515, 1516, 1518, 1519, 1521, 1524, 1525, 1528, 1529, 1531, 1532,
		1533, 1535, 1536, 1537, 1541, 1542, 1543, 1545, 1546, 1547, 1548, 1549, 1551, 1552, 1553,
		1554, 1555, 1556, 1557, 1558, 1561, 1562, 1563, 1564, 1565, 1567, 1569, 1571, 1573, 1574,
		1576, 1578, 1580, 1582, 1583, 1584, 1585, 1588, 1589, 1590, 1591, 1592, 1594, 1595, 1596,
		1597, 1600, 1601, 1603, 1605, 1606, 1609, 1611, 1612, 1614, 1615, 1617, 1618, 1621, 1622,
		1624, 1625, 1627, 1628, 1629, 1632, 1633, 1634, 1635, 1636, 1637, 1638, 1640, 1641, 1644,
		1646, 1647, 1648, 1649, 1650, 1652, 1655, 1657, 1658, 1660, 1663, 1665, 1666, 1667, 1668,
		1669, 1670, 1672, 1673, 1676, 1677, 1679, 1681, 1682, 1683, 1684, 1685, 1686, 1692, 1693,
		1694, 1695, 1696, 1698, 1699, 1703, 1704, 1707, 1709, 1710, 1711, 1712, 1713, 1715, 1716,
		1719, 1720, 1721, 1722, 1723, 1724, 1725, 1726, 1727, 1728, 1729, 1730, 1732, 1733, 1734,
		1735, 1737, 1738, 1739, 1740, 1741, 1742, 1743, 1744, 1748, 1752, 1753, 1756, 1757, 1758,
		1762, 1764, 1765, 1768, 1770, 1771, 1772, 1773, 1774, 1775, 1777, 1778, 1780, 1781, 1783,
		1784, 1786, 1787, 1788, 1789, 1790, 1791, 1792, 1793, 1795, 1796, 1797, 1798, 1800, 1801,
		1803, 1805, 1809, 1810, 1811, 1813, 1814, 1815, 1816, 1819, 1820, 1821, 1822, 1823, 1824,
		1826, 1828, 1829, 1830, 1831, 1832, 1833, 1835, 1837, 1838, 1839, 1840, 1841, 1844, 1846,
		1847, 1848, 1849, 1851, 1852, 1856, 1857, 1859, 1860, 1861, 1862, 1863, 1865, 1866, 1867,
		1868, 1871, 1873, 1875, 1876, 1877, 1878, 1880, 1881, 1882, 1883, 1884, 1885, 1886, 1887,
		1888, 1889, 1890, 1891, 1895, 1899, 1900, 1901, 1902, 1903, 1904, 1905, 1907, 1910, 1915,
		1918, 1920, 1921, 1923, 1927, 1928, 1932, 1934, 1935, 1937, 1938, 1940, 1941, 1942, 1943,
		1946, 1947, 1948, 1950, 1951, 1952, 1953, 1954, 1955, 1958, 1960, 1964, 1965, 1969, 1970,
		1971, 1972, 1974, 1975, 1978, 1979, 1981, 1982, 1983, 1986, 1988, 1990, 1991, 1992, 1993,
		1995, 1997, 1998, 1999, 2001, 2002, 2003, 2004, 2009, 2010, 2011, 2012, 2016, 2020, 2022,
		2027, 2028, 2029, 2030, 2031, 2032, 2034, 2035, 2039, 2040, 2041, 2043, 2046}

	recursion := BinarySearchRecursion(smallarray, 10, 0, len(smallarray)-1)
	fmt.Printf("Found the element at %d from smallarray using the BinarySearchRecursion algorithm\n", recursion)

	recursion = BinarySearchRecursion(bigarray, 52, 0, len(bigarray)-1)
	fmt.Printf("Found the element at %d from bigarray using the BinarySearchRecursion algorithm\n", recursion)

	/*
		incremental := BinarySearchIncremental(smallarray, 50, 0, len(smallarray)-1)
		fmt.Printf("Found the element at %d from smallarray using the BinarySearchInvariant algorithm\n", incremental)

		incremental = BinarySearchIncremental(smallarray, 50, 0, len(smallarray)-1)
		fmt.Printf("Found the element at %d from bigarray using the BinarySearchInvariant algorithm\n", incremental)
	*/
}

// BinarySearchRecursion - Binary search via Recursion
// Does 2 comparisons
func BinarySearchRecursion(array []int, target, lowIndex, highIndex int) int {
	if highIndex < lowIndex {
		return -1
	}
	mid := int((lowIndex + highIndex) / 2)
	if array[mid] > target {
		return BinarySearchRecursion(array, target, lowIndex, mid)
	} else if array[mid] < target {
		return BinarySearchRecursion(array, target, mid+1, highIndex)
	} else {
		return mid
	}
}

// BinarySearchIncremental - Binary search via Incremental
// Does incremental comparisons very costly
func BinarySearchIncremental(array []int, target, lowIndex, highIndex int) int {
	startIndex := lowIndex
	endIndex := highIndex
	var mid int
	for startIndex < endIndex {
		mid = int((startIndex + endIndex) / 2)
		if array[mid] > target {
			endIndex = mid
		} else if array[mid] < target {
			startIndex = mid
		} else {
			return mid
		}
	}
	return -1
}

// BinarySearchIndexOfMinimumRotatedArray : Invariant: A[l] <= key and A[r] > key
// Boundary: |r - l| = 1
// Input: A[l ... r-1]
func BinarySearchIndexOfMinimumRotatedArray(array []int, target, lowIndex, highIndex int) int {
	var mid int
	if array[lowIndex] <= array[highIndex] {
		return -1
	}
	for lowIndex <= highIndex {
		if lowIndex == highIndex {
			return -1
		}
		mid = int(lowIndex + (highIndex-1)/2)
		if array[mid] < array[highIndex] {
			highIndex = mid
		} else {
			lowIndex = mid + 1
		}
	}
	return -1
}