My binary search function in Python is not working

Question

I am developing a Binary Search function in Python. It is not working and shows up as a nothing coming up.

I have tried to set up the logic with Pseudocode and my teacher says that it works, however they have no idea why the algorithm and function are doing what they are doing. I have skinned the fat on my Pseudocode and multiple people have been able to fix my problem.

def binary_search(array,item):
    start_point = 0
    end_point = len(array)
    mid_point = int((start_point + end_point) / 2)
    array.sort()
    print(array)it
    while array[mid_point] != item:
        if array[mid_point] > item:
            start_point = mid_point
        elif array[mid_point] < item:
            end_point = mid_point
    if array[mid_point] == item:
        print(mid_point)

binary_search([0,99,2,6,4,8],7)

I want this function to work so that when you enter an array and a search term it shows where there is in the array (the index value)

Welcome to StackOverflow. Here's a guide on how to ask questions. stackoverflow.com/help/how-to-ask. More specifically, what is your expected output from entering the array above. — Spinor8
– Spinor8, Commented Mar 28, 2019 at 5:57

Paul M. · Accepted Answer · 2019-03-28 06:15:05Z

2

You aren't actually doing anything with start_point and end_point.

Also, if the element at the middle is greater than the item you're looking for, wouldn't you want to move the end_point to the middle? Same thing goes for your elif-statement - if the element in the middle is less than the item you're looking for, you'd want to move the start_point to the middle.

answered Mar 28, 2019 at 6:15

Paul M.

10.8k2 gold badges11 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

gaurav · Accepted Answer · 2019-03-28 06:26:43Z

Firstly before solving problem let's discuss binary search,

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half.

Here you need to change midpoint every time when while loop completes it's single loop and then you need to check if item is in lower half or upper half if it is present in lower half then you need to change end-point not start-point and if in upper half then change lower-point

And one important thing, in your while condition if element is not present then it will be in infinite loop so your while loop condition must be while(end_point > start_point) because we are changing points in each loop.

Code for reference:

def binary_search(array,item):
    start_point = 0
    end_point = len(array)
    array.sort()
    print(array)
    while end_point > start_point:
        mid_point = int((start_point + end_point) / 2)
        if array[mid_point] < item:
            start_point = mid_point+1
        elif array[mid_point] > item:
            end_point = mid_point-1
        elif array[mid_point] == item:
            print(mid_point)
            return
    print("ELement is not present")

binary_search([0,99,2,6,7,8],3)

Maged Saeed · Accepted Answer · 2019-03-28 06:30:29Z

you are doing a good job with this pseudo code, However, it is not complete. Consider the following points:

You need to add a condition to the while loop to stop if the mid_point becomes zero.
You need also to update the value of mid_point at each branch of the if condition.
You need to subtract 1 from the first assignment of mid_point since python is a zero-indexed language.

Here is a working version of the code:

def binary_search(array,item):
    start_point = 0
    end_point = len(array)
    mid_point = int((start_point + end_point) / 2)-1
    array.sort()
    print('array after sorting:',array)

    while mid_point < len(array) and mid_point > 0:
        if array[mid_point] == item:
            print('item found at cell:',mid_point,', Note that array index starts from zero!')
            return
        elif array[mid_point]>item:
            end_point = mid_point
            mid_point = int((start_point + end_point) / 2)
        else:
            start_point = mid_point
            mid_point = int((start_point + end_point) / 2)
    print('number not found!')
    return


binary_search([0,99,2,6,4,8,12,13,17,15],8)

Devisha Mehta · Accepted Answer · 2019-03-28 06:13:33Z

0

What is going wrong is that the while loop is comparing the same value of array[mid_point] at every iteration, thus ending into an infinite loop if the condition satisfies.

Binary Search is a recursive approach and iterates over lesser elements of the same list with every iteration until the required element's index is obtained, if it is present in the list. Your code will work if you slice the array and call binary_search recursively passing the newer list as the argument. The while loop then can be replaced by a simple if condition.

For more reference, check this link and compare with your function to understand the difference. :)

answered Mar 28, 2019 at 6:13

Devisha Mehta

114 bronze badges

Collectives™ on Stack Overflow

My binary search function in Python is not working

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related