Python Forum

I am trying a binary search algorithm to search for an element in a list, but the low and high intervals should not be the index in list but rather the value of the item in the list. I have written a code for that and I've used the enumeration function but that is not efficient. Any alternatives I can implement this?

myList = [1,4,5,6,9,10,12,14,16,19,20,22,23,24,29,30]#list(range(1, 51))  #Create list between 0-100
search = int(input("Search For Number: "))  #Enter number to search for
low = int(input("Lower Interval: "))    #starting point in list
high = int(input("Higher Interval: "))  #end point in list

#look for closest index to low in the list
for index, item in enumerate(myList):
        if(item >= low):
            low = index
            break

#look for closest index to high in the list
for index, item in enumerate(myList):
        if(item >= high):
            high = index
            break

def binary(myList, low, high, search):
    
    print(myList[low:high], "\n")
    
    mid = int((low+high)/2) #mid point of two intervals within list

    if(low>high):   # Base condition: if number not in list, the lower will keep increasing
        print("Number not found!")
        return False            
    else:    
            if (search == myList[mid]): #base condition if number is the mid value
                print("number found in index number",mid)
                return mid
            elif (search < myList[mid]):    #return list from lower interval to mid point
                return binary(myList, low, mid-1, search)
            else:   #return list from mid point to higher interval
                return binary(myList, mid+1, high, search)


binary(myList, low, high, search)

(Nov-04-2016, 12:31 AM)salmanfazal01 Wrote: [ -> ]I've used the enumeration function but that is not efficient.

Obviously if you use a O(n) method to attempt to speed up a O(logn) algorithm it isn't going to help. Basically your only choice to find those indexes is also a binary search. You can use the bisect module.

from bisect import bisect

myList = [1,4,5,6,9,10,12,14,16,19,20,22,23,24,29,30]

low = bisect(myList, int(input("Enter number with which to bisect: ")))

print(low)

Honestly I don't think this will help one bit, but it at least keeps the overall complexity of your code down to O(logn). O(logn) is incredibly fast so I don't think this will make any noticeable change whatsoever; just search the whole list. Also using an implementation of binary search to implement binary search is a little silly to say the least.

salmanfazal01

Mekire