#5.py).

# This is the Binary Search. Its complexity is O(lg n), so it is a lot faster
# than linear search. BUT, the Binary Search needs you to give it a list that is
# in ascending order (i.e., a SORTED list)



def binsearch (x, numberList):


        low = 0                                          # index of first number in list or sublist
        
        high = len(numberList) - 1                       #     "     "   last     "        "   "    "     " 

        while  low  <= high:                             # when low == high the sublist size is 1

            n = high - low + 1    
            
            print(numberList[low:high+1],"     low:",low,"    high:",high, "    n:",n, end = "")
            

            n = high - low + 1                            # high and low keep changing

            mid = low + n // 2                            # get index of "middle" element in list

            print("     mid = ",mid)

            if (x == numberList[mid]):                    # is there a match?

                print("Found", x," at index", mid);

                return mid                                # if yes, return the index it was found in

            elif (x < numberList[mid]):                   # should we search the left sublist?

                print("Search the left sublist")

                high = mid - 1                            # if so, update high, leave low the same

            else:

                print("Search the right sublist")
                
                low = mid + 1                             # else we must search the right sublist
                                                          # update low, leave high the same

                                                                           
        print("Not in list!")
              
        return (-1)          # we did not return mid in the loop; if we reached here it means
                             # that the loop ended at a sublist of size 1 with no match. Hence
                             # we must return -1 to show that the binsearch failed to find x