Q:

Python program for Binary Search

mahmoud2506
Save to bookmark
|
2022-05-22
|
  211 
0

Binary search is a searching algorithm which is used to search a number in a sorted array or list.

Description:

Binary search uses Decrease and Conquer Algorithm. In this algorithm original problem is decreased by a constant factor and a sub-problem is created and then the sub-problem is further solved to get the solution of the original problem. This process keeps on going unless the problem is solved or no further division is possible.

Procedure for Binary Search:

    First sort the array (ascending or descending totally depends upon user)
    Start = 0, end = length (array) – 1
    Mid = (start + end) / 2
    While start is less than end
        If array[mid] == number
            Print number found and exit
        If array[mid] > number
            End = mid – 1
            Mid = (start + end) / 2
        If array[mid] < number
            Start = mid + 1
            Mid = (start + end) / 2
    End of while

Time Complexity : O(logn)

Note: For binary search array or list needs to be sorted before searching otherwise one may not get correct result.

Python programming, examples, Python programming examples,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-22
need an explanation for this answer? contact us directly to get an explanation for this answer

Python code for binary search

def binary_search(l, num_find):
    '''
    This function is used to search any number.
    Whether the given number is present in the
    list or not. If the number is present in list
    the list it will return TRUE and FALSE otherwise.
    '''
    start = 0
    end = len(l) - 1
    mid = (start + end) // 2
    
    # We took found as False that is, initially
    # we are considering that the given number
    # is not present in the list unless proven
    found = False
    position = -1

    while start <= end:
        if l[mid] == num_find:
            found = True
            position = mid
            break
        
        if num_find > l[mid]:
            start = mid + 1
            mid = (start + end) // 2
        else:
            end = mid - 1
            mid = (start + end) // 2

    return (found, position)

    # Time Complexity : O(logn)


# main code
if __name__=='__main__':
    
    l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    num = 6
    found = binary_search(l, num)
    if found[0]:
        print('Number %d found at position %d'%(num, found[1]+1))
    else:
        print('Number %d not found'%num)

Output

Number 6 found at position 7

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Python: Data Structures – Programs, Exercises, Practice, Solution
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Breadth First Search for a Graph in Python... >>
<< Python program for Linear Search...