GCK/ binarysearch

from random import randint


p=[randint(0,10000) for i in range (1000)]
#p_fix is a sorted test list with duplicates
p_fix=[8, 15, 47, 52, 76, 87, 90, 94, 133, 138, 144, 148, 150, 150, 168, 172, 177, 180, 202, 205, 254, 265, 280, 285, 288, 290, 295, 301, 309, 318, 325, 325, 339, 363, 369, 374, 377, 385, 422, 423, 428, 438, 439, 452, 473, 510, 526, 538, 548, 560, 565, 581, 608, 647, 654, 661, 664, 671, 695, 705, 707, 707, 714, 723, 729, 747, 752, 755, 765, 768, 770, 770, 775, 789, 822, 824, 843, 846, 862, 880, 891, 900, 927, 949, 955, 959, 967, 967, 973, 975, 991, 1014, 1031, 1034, 1041, 1044, 1045, 1067, 1069, 1069, 1071, 1086, 1142, 1149, 1160, 1167, 1174, 1178, 1181, 1197, 1198, 1200, 1201, 1209, 1217, 1234, 1244, 1254, 1257, 1257, 1277, 1278, 1280, 1286, 1294, 1294, 1297, 1305, 1337, 1350, 1358, 1406, 1411, 1421, 1426, 1430, 1436, 1451, 1471, 1474, 1475, 1476, 1497, 1500, 1512, 1527, 1563, 1566, 1589, 1596, 1597, 1631, 1636, 1650, 1660, 1674, 1676, 1681, 1696, 1697, 1714, 1727, 1730, 1738, 1790, 1804, 1806, 1835, 1839, 1847, 1847, 1849, 1852, 1866, 1875, 1880, 1886, 1905, 1917, 1926, 1930, 1947, 1959, 1989, 2006, 2024, 2029, 2040, 2041, 2042, 2051, 2056, 2060, 2067, 2068, 2070, 2077, 2080, 2084, 2105, 2113, 2116, 2132, 2146, 2153, 2194, 2216, 2218, 2220, 2224, 2234, 2261, 2301, 2304, 2310, 2312, 2316, 2317, 2322, 2322, 2326, 2339, 2343, 2360, 2360, 2372, 2377, 2379, 2383, 2392, 2407, 2409, 2430, 2436, 2438, 2438, 2444, 2447, 2452, 2482, 2501, 2511, 2520,   2525, 2539, 2553, 2566, 2576, 2593, 2598, 2627, 2632, 2642, 2644, 2651, 2657, 2676, 2689, 2694, 2695, 2719, 2723, 2741, 2763, 2764, 2772, 2788, 2788, 2791, 2794, 2802, 2811, 2820, 2852, 2858, 2881, 2883, 2886, 2889, 2895, 2912, 2914, 2922, 2929, 2949, 2961, 2962, 2973, 2973, 2985, 2985, 2986, 2990, 2998, 3017, 3036, 3037, 3040, 3047, 3060, 3066, 3095, 3096, 3110, 3118, 3147, 3150, 3158, 3159, 3159, 3163, 3188, 3193, 3205, 3210, 3217, 3225, 3225, 3230, 3235, 3238, 3250, 3261, 3270, 3278, 3286, 3287, 3292, 3296, 3301, 3303, 3308, 3312, 3312, 3332, 3342, 3351, 3352, 3362, 3375, 3376, 3387, 3398, 3403, 3404, 3420, 3424, 3474, 3480, 3481, 3483, 3492, 3492, 3493, 3504, 3508, 3521, 3534, 3553, 3570, 3585, 3589, 3593, 3596, 3611, 3638, 3640, 3642, 3644, 3645, 3655, 3656, 3668, 3684, 3719, 3724, 3738, 3740, 3745, 3763, 3784, 3797, 3802, 3807, 3810, 3817, 3824, 3829, 3831, 3848, 3857, 3859, 3865, 3865, 3867, 3873, 3875, 3883, 3887, 3894, 3905, 3928, 3932, 3938, 3951, 3958, 3966, 3969, 3972, 3975, 3984, 3990, 4002, 4007, 4023, 4049, 4083, 4103, 4113, 4131, 4145, 4152, 4171, 4173, 4181, 4184, 4192, 4200, 4202, 4216, 4224, 4240, 4248, 4263, 4282, 4292, 4309, 4318, 4320, 4322, 4327, 4347, 4350, 4367, 4368, 4371, 4374, 4375, 4375, 4393, 4401, 4404, 4408, 4415, 4419, 4431, 4435, 4452, 4453, 4465, 4480, 4489, 4491, 4499, 4547, 4548, 4551, 4563, 4585, 4595, 4601, 4620, 4620, 4623, 4632, 4633, 4644, 4649, 4652, 4656, 4660, 4664, 4670, 4672, 4689, 4705, 4729, 4730, 4740, 4741, 4747, 4748, 4758, 4764, 4788, 4799, 4799, 4803, 4814, 4828, 4831, 4838, 4841, 4842, 4847, 4857, 4879, 4907, 4912, 4936, 4949, 4963, 4981, 4997, 5006, 5011, 5037, 5052, 5064, 5065, 5070, 5078, 5081, 5096, 5099, 5140, 5186, 5199, 5216, 5219, 5225, 5226, 5228, 5254, 5256, 5263, 5269, 5285, 5288, 5312, 5353, 5364, 5377, 5402, 5415, 5418, 5450, 5482, 5495, 5498, 5510, 5512, 5512, 5539, 5552, 5570, 5599, 5601, 5621, 5622, 5626, 5636, 5647, 5650, 5653, 5657, 5660, 5668, 5673, 5680, 5685, 5688, 5694, 5705, 5711, 5722, 5737, 5743, 5764, 5773, 5791, 5796, 5810, 5826, 5828, 5851, 5863, 5864, 5866, 5868, 5893, 5903, 5914, 5929, 5953, 5959, 5965, 5971, 5976, 5979, 5984, 5987, 5990, 6009, 6017, 6022, 6025, 6059, 6071, 6086, 6089, 6101, 6126, 6129, 6133, 6167, 6171, 6177, 6188, 6225, 6228, 6263, 6267, 6297, 6310, 6332, 6345, 6347, 6367, 6375, 6382, 6390, 6404, 6412, 6423, 6427, 6431, 6439, 6441, 6445, 6454, 6460, 6469, 6474, 6529, 6532, 6535, 6542, 6573, 6584, 6588, 6626, 6652, 6658, 6659, 6676, 6687, 6690, 6690, 6690, 6694, 6694, 6695, 6709, 6710, 6716, 6727, 6727, 6733, 6740, 6748, 6760, 6766, 6768, 6778, 6789, 6812, 6818, 6820, 6830, 6835, 6841, 6869, 6870, 6891, 6895, 6899, 6905, 6914, 6925, 6940, 6955, 6958, 6996, 7023, 7024, 7038, 7046, 7056, 7071, 7073, 7073, 7080, 7103, 7113, 7119, 7120, 7120, 7127, 7129, 7132, 7134, 7143, 7148, 7152, 7160, 7184, 7198, 7199, 7199, 7201, 7212, 7212, 7237, 7244, 7260, 7275, 7292, 7308, 7315, 7317, 7320, 7321, 7334, 7353, 7358, 7389, 7400, 7414, 7418, 7419, 7440, 7446, 7458, 7463, 7478, 7512, 7514,        7519, 7519, 7525, 7535, 7546, 7559, 7570, 7572, 7590, 7606, 7611, 7617, 7621, 7639, 7655, 7674, 7696, 7700, 7733, 7738, 7756, 7763, 7772, 7786, 7795, 7798, 7799, 7799, 7829, 7835, 7835, 7841, 7843, 7848, 7859, 7864, 7879, 7904, 7922, 7922, 7932, 7937, 7953, 7959, 7970, 7981, 7982, 7988, 7994, 7995, 7996, 7996, 8000, 8001, 8006, 8011, 8011, 8015, 8019, 8030, 8031, 8033, 8043, 8052, 8059, 8059, 8062, 8065, 8067, 8068, 8070, 8077, 8091, 8123, 8172, 8174, 8177, 8179, 8182, 8186, 8192, 8196, 8212, 8229, 8229, 8247, 8256, 8257, 8259, 8276, 8284, 8290, 8293, 8298, 8344, 8356, 8357, 8368, 8370, 8376, 8383, 8384, 8388, 8414, 8423, 8427, 8440, 8454, 8469, 8536, 8537, 8537, 8561, 8562, 8567, 8569, 8574, 8596,  8605, 8608, 8657, 8681, 8687, 8710, 8724, 8730, 8751, 8756, 8770, 8770, 8779, 8806, 8813, 8815, 8816, 8832, 8838, 8839, 8846, 8856, 8856, 8863, 8866, 8868, 8872, 8881, 8892, 8895, 8906, 8910, 8924, 8961, 9001, 9006, 9018, 9030, 9038, 9069, 9070, 9079, 9097, 9117, 9123, 9133, 9149, 9181, 9213, 9235, 9240, 9246, 9251, 9253, 9277, 9287, 9301, 9311, 9325, 9350, 9368, 9373, 9388, 9393, 9394, 9397, 9402, 9413, 9414, 9415, 9417, 9424, 9440, 9454, 9455, 9471, 9474, 9501, 9506, 9512, 9520, 9548, 9548, 9552, 9573, 9574, 9590, 9596, 9601, 9607, 9608, 9610, 9614, 9620, 9640, 9640, 9666, 9694, 9699, 9701, 9725, 9729, 9737, 9758, 9771, 9775, 9785, 9789, 9793, 9794, 9815, 9821, 9845, 9846, 9848, 9863, 9867, 9874, 9876, 9892, 9896, 9897, 9905, 9928, 9930, 9936, 9939, 9945, 9960, 9962, 9962, 9967, 9967, 9970, 9991]

sorted_list=sorted(p)

def binary_search(sortedlist,value):

    left=0
    print("leftmost: {}".format(left))
    right=len(sortedlist) -1
    print("rightmost: {}".format(right))
    #mid=(left+right)//2
    position_list=[]
    list_of_mid=[]
    list_of_difference=[]
    while (left <= right)== True :
        mid=(left+right)//2
        if sortedlist[mid]>value:
            right=mid-1
            closest_right=sortedlist[mid-1]-value
# we create a list of list of differences with (index, item   of the list at that index, and the difference between the item and value)
            list_of_difference.append([mid-1,sortedlist[mid-1], closest_right])

        elif sortedlist[mid]<value:
            left=mid +1
            closest_left=sortedlist[mid-1]-value
            list_of_difference.append([mid+1,sortedlist[mid-1], closest_left])

        else:
            for n in range(10): # we add all indices of duplicates in a list
                if sortedlist[mid-n]==value:
                    list_of_mid.append(mid-n)
                elif sortedlist[mid+n]==value:
                    list_of_mid.append(mid+n)
                    position_list.append(mid)
            return sorted(list_of_mid)

# if value is not found then the list of differences will be sorted by the absolute value of the third list item which is the difference
# between the value we looked for with the closest neighbours (mid) determined along the search.

    if len(list_of_mid)==0:
        sorted_differences=sorted(list_of_difference, key=lambda x: abs(x[2]) , reverse=True)
        print("value {} is not found but the closest value is at (index,list[index],(list[index]-value)) of {}".format(value,sorted_differences[-1]))
    return False


#value=95
#position=binary_search(sorted_list,95)
#value=1207
value=6690
position=binary_search(p_fix,6690)
print("Value {} is found at position(s) {}".format(value,position))