Incorrect binary search code in python

I am constantly getting the wrong output in my binary search program. The output is always None even when the key element is present. Have a look at my code and help, please.

guess=1
def binary_search(n,key):
    low=0
    high=len(n)-1
    
    while(low <= high):
        mid=(low+high)//2
        guess=n[mid]
        if(guess==key):
            return mid
        elif (guess<key):
            high=mid-1
        elif(guess>key):
            low=mid+1
    return None

n=[1,3,5,7,9]
print(binary_search(n,3)) 

Incorrect binary search code in python

snakecharmerb

39.1k10 gold badges77 silver badges124 bronze badges

asked Sep 23, 2021 at 15:44

Incorrect binary search code in python

3

Your search conditions are wrong. if guess>key then you need to decrease the guess my setting high=mid-1 and increase the guess with low=mid+1 if guess<key.

guess=1
def binary_search(n,key):
    low=0
    high=len(n)-1
    
    while(low <= high):
        mid=(low+high)//2
        guess=n[mid]
        if(guess==key):
            return mid
        elif (guess>key):
            high=mid-1
        elif(guess<key):
            low=mid+1
    return None

n=[1,3,5,7,9]
print(binary_search(n,3))

answered Sep 23, 2021 at 15:50

Incorrect binary search code in python

Albin PaulAlbin Paul

3,2332 gold badges14 silver badges28 bronze badges

4

View Discussion

Improve Article

Save Article

  • Read
  • Discuss
  • View Discussion

    Improve Article

    Save Article

    In a nutshell, this search algorithm takes advantage of a collection of elements that is already sorted by ignoring half of the elements after just one comparison. 

    1. Compare x with the middle element.
    2. If x matches with the middle element, we return the mid index.
    3. Else if x is greater than the mid element, then x can only lie in the right (greater) half subarray after the mid element. Then we apply the algorithm again for the right half.
    4. Else if x is smaller, the target x must lie in the left (lower) half. So we apply the algorithm for the left half.

    Recursive :

    Python3

    def binary_search(arr, low, high, x):

        if high >= low:

            mid = (high + low) // 2

            if arr[mid] == x:

                return mid

            elif arr[mid] > x:

                return binary_search(arr, low, mid - 1, x)

            else:

                return binary_search(arr, mid + 1, high, x)

        else:

            return -1

    arr = [ 2, 3, 4, 10, 40 ]

    x = 10

    result = binary_search(arr, 0, len(arr)-1, x)

    if result != -1:

        print("Element is present at index", str(result))

    else:

        print("Element is not present in array")

    Output:  

    Element is present at index 3

    Time Complexity: O(log n)

    Auxiliary Space: O(logn)     [NOTE: Recursion creates Call Stack]

    Iterative:
     

    Python3

    def binary_search(arr, x):

        low = 0

        high = len(arr) - 1

        mid = 0

        while low <= high:

            mid = (high + low) // 2

            if arr[mid] < x:

                low = mid + 1

            elif arr[mid] > x:

                high = mid - 1

            else:

                return mid

        return -1

    arr = [ 2, 3, 4, 10, 40 ]

    x = 10

    result = binary_search(arr, x)

    if result != -1:

        print("Element is present at index", str(result))

    else:

        print("Element is not present in array")

    Output:  

    Element is present at index 3

    Time Complexity: O(log n)

    Auxiliary Space: O(1)
    Please refer to the article Binary Search for more details!
     


    What is binary search Explain with example in Python?

    Binary search is a searching algorithm which is used to search an element from a sorted array. It cannot be used to search from an unsorted array. Binary search is an efficient algorithm and is better than linear search in terms of time complexity. The time complexity of linear search is O(n).

    How do you write a binary search program in Python?

    Implement a Binary Search in Python.
    # Iterative Binary Search Function method Python Implementation..
    # It returns index of n in given list1 if present,.
    # else returns -1..
    def binary_search(list1, n):.
    low = 0..
    high = len(list1) - 1..
    mid = 0..
    while low <= high:.

    How do you know if a binary search is not working?

    How to identify a Binary Search problem?.
    I. Order Agnostic Search :.
    II. Find the range of occurrence of an element in a sorted array :.
    III. Frequency of an element in a sorted array :.
    IV. Find the number of times a sorted array is rotated :.
    V. ... .
    VI. ... .
    VII. ... .
    Floor: Largest element smaller than or equal to the key..

    What is binary search method in Python?

    Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half, again taking the middle element to compare to the target value and repeating this until the target value is found.

    Tải thêm tài liệu liên quan đến bài viết Incorrect binary search code in python