Python binary search lib

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

learn more about Binary Search in Python!

gasampaiosouza/python-binarySearch

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

readme.md

Hey 👋
~ let’s talk about binary search today!

So, what is Binary Search?

«Binary Search is a search algorithm that finds the position of a target value within a sorted array.»
~ Wikipedia

It works in every programming language, but i’m gonna show how it works with Python.

def loop_search(arr, target): for pos in arr: # loop through the array if arr[pos] == target: # if we find our target return arr.index(target) # return its index return False # else, return false loop_search( [1, 2, 3, 4, 5], 4 ) # 3

Okay, it’s a basic thing we all know how to do. But what if we want to do it with a LARGE amount of elements? For example:

import random import math # create an array with numbers between 1 and 500, with 10.000 numbers in it someArray = [math.floor(random.randint(1, 500)) for _ in range(10000)] loop_search( someArray, 4 ) # input will be random in this case

Obs: This [for _ in range(10000)] is called List Comprehension, if you want to learn more!

You see? It’s going to loop through every element until it finds the target we want. What if our target is in len(someArray) position? It will loop through it 10.000 times!! You don’t wanna do that.

That’s simple! We do the same thing we did but with Binary Search.

Ok, let’s pretend we have a Phone Book, those large ones. We want to call Michael, just because we want to hang out with him.
~ How can we do this thing? Let’s do this algorithmically:

• We take the Phone Book
• Search for the M letter
• Find Michael on page 236
• Call him

That’s simple, right? But what if we do the same thing the way we did with the code?
~ It’s gonna be like this:

We’re going to do this until we reach page 236 , it’s a lot of work.

So, to do less, we need to do exactly what we did in the first example, but in code.

The best way to do this is writing it in human language first, with as many details as you can. For example:

• Take Phone Book
• Go to the center of the phone book
• Page word is M?
  • No
    • Page word comes first than M on alphabet?
      • Yes
        • So we can discard all the pages to the left!
        • So we can discard all the pages to the right!
        • Let’s search for Michael here!

        That’s basically what we’re going to do! but with numbers!

        # we have to import math, because "mid" must be an integer import math # pretend we wanna find 30's index in some array def binary_search(arr, target): arr.sort() # we MUST sort it # define left-side as the first "book's page" left = 0 # define right-side as the array's length (last book's page) right = len(arr) - 1 # so, while we don't find our target while left  right: # we define mid, so we can discard left or right mid = math.floor((left + right) / 2) # arr[mid] = 18, target = 30 if target > arr[mid]: # we can discard all the left pages left = mid + 1 # arr[mid] = 36, target = 30 elif target  arr[mid]: # we can discard all the left pages right = mid - 1 # we find it! else: # return it's index return arr.index(target)

        That’s it! Let’s test this code:

        binary_search( [1, 2, 3, 4, 5], 3 ) # 2 binary_search( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 7 ) # 6 binary_search( [3, 2, 5, 9, 1, 6, 10], 10 ) # 6, because it's sorted: [1, 2, 3, 5, 6, 9, `10`] # It also works FAST with an array with 50.000 items for example. If you want to find some item index there!

        Hey, item’s index isn’t the only thing you can return from this function. Be creative!

        Hope you learned something about Binary Search!

        Obs: Binary Search isn’t the only kind of search we have in programming languages, you can see some of’em here.

        If you want to know more about this, or if you didn’t understand something here, you can check some websites for more information:

        • Real Python (Binary Search)
        • Geek for Geeks (Binary Search)
        • CS50 CS50 is a Harvard’s course, that talks about it and much more. I strongly recommend.

        Источник

        linear search and binary search in Python program

        In this Python tutorial, we will discuss, linear search and binary search in Python program. This tutorial will walk you through implementing two of the most fundamental search algorithms: linear search and binary search in Python. You will also learn to implement binary search without using functions.

        linear search and binary search in Python

        Searching is a common operation in computer science, where you need to find a particular value from a collection of values. Two common algorithms for this operation are linear search and binary search.

        Linear Search:

        • In linear search, you start from the first element and compare each element with the target value until you find a match.
        • Time Complexity: O(n)

        How it works:

        1. Start from the first element of the array.
        2. Compare the target value with the current element.
        3. If it matches, return the index.
        4. If not, move to the next element.
        5. Repeat steps 2-4 until you find the target or reach the end of the array.

        Performance:

        • Time complexity is O(n) because, in the worst-case scenario, it checks each element in the array.
        • No requirement for the array to be sorted.

        Binary Search:

        • In binary search, the array must be sorted. You repeatedly divide the array into halves until the value is found.
        • Time Complexity: O(log n)

        How it works:

        1. The array must be sorted before using binary search.
        2. Start by setting two pointers, one at the start (left) and one at the end (right) of the array.
        3. Find the middle element.
        4. Compare the middle element with the target.
        5. If it matches, return the index.
        6. If the target is larger than the middle element, move the left pointer to the middle + 1.
        7. If the target is smaller than the middle element, move the right pointer to the middle – 1.
        8. Repeat steps 3-7 until you find the target or the pointers cross (left > right).

        Performance:

        • Time complexity is O(log n) because it effectively halves the search space with each iteration.
        • Requires the array to be sorted.

        Linear Search in Python

        Implementing Linear Search

        Here’s a step-by-step guide to implementing a linear search algorithm in Python:

        def linear_search(arr, target): # Loop through each element in the array for index, element in enumerate(arr): # If the element matches the target, return the index if element == target: return index # If the loop finishes, the target was not found return -1 

        Example: Linear Search Program in Python

        Let’s write a Python program for linear search to find the index of a target value in an array.

        def linear_search(arr, target): for index, element in enumerate(arr): if element == target: return index return -1 # Example array and target value arr = [4, 2, 7, 1, 9, 3] target = 7 # Call the linear_search function index = linear_search(arr, target) # Output the result if index != -1: print(f"Element found at index ") else: print(f"Element not found in the array") 

        

        Binary Search in Python

        Implementing Binary Search with a Function

        Here’s a step-by-step guide to implementing binary search using a function:

        def binary_search(arr, target): left, right = 0, len(arr) - 1 # Continue the search while the left index is less than or equal to the right index while left  

        Example: Binary Search Program in Python

        Let’s see a Python program to implement binary search using the above function.

        def binary_search(arr, target): left, right = 0, len(arr) - 1 while left found at index ") else: print(f"Element not found in the array") 

        You can see the output like below:

        

        Implement Binary Search Without a Function

        Here’s how you can write a Python program to implement binary search without using a function.

        Example: Binary Search in Python Without a Function

        # Example sorted array and target value arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] target = 6 # Set initial left and right indices left, right = 0, len(arr) - 1 # Binary search without function while left found at index ") break # If target is greater, ignore the left half elif arr[mid] < target: left = mid + 1 # If target is smaller, ignore the right half else: right = mid - 1 else: print(f"Element not found in the array") 

        You can see the output below in the screenshot.

        

        Linear Search and Binary Search in Python

        Here is a comparison of Linear Search and Binary Search in Python in a tabular format:

        Aspect	Linear Search	Binary Search
        Algorithm Type	Sequential Search	Interval Search
        How it works	Sequentially checks each element for a match	Repeatedly divides the search interval in half
        Sorted Data Required	No, works on both sorted and unsorted arrays	Yes, only works on sorted arrays
        Time Complexity	O(n)	O(log n)
        Space Complexity	O(1)	O(1)
        Implementation	Easier	Slightly more complex
        Performance	Slower for large datasets	Faster for large datasets
        Best-case Scenario	O(1), when the element is at the first position	O(1), when the element is at the middle position
        Worst-case Scenario	O(n), when the element is at the last position or not present	O(log n)
        Use Cases	Small datasets, unsorted data	Large datasets, sorted data

        This table summarizes the key differences between linear search and binary search algorithms in Python.

        Conclusion

        This tutorial has covered how to implement linear search and binary search in Python, including examples with and without using functions. Whether you’re looking to write a python program to implement linear search and binary search, or specifically focusing on binary search in Python without using a function, this tutorial has you covered.

        I am Bijay Kumar, a Microsoft MVP in SharePoint. Apart from SharePoint, I started working on Python, Machine learning, and artificial intelligence for the last 5 years. During this time I got expertise in various Python libraries also like Tkinter, Pandas, NumPy, Turtle, Django, Matplotlib, Tensorflow, Scipy, Scikit-Learn, etc… for various clients in the United States, Canada, the United Kingdom, Australia, New Zealand, etc. Check out my profile.

        Источник