bigscal-logo
  • bigscal-logo
  • Services
    • Software Development
          • Software Product Development
            • SaaS Consulting
            • MVP Development
            • Startup Product Development
            • Product UI/UX Design
            • Startup Consulting
          • Information Technology Consulting
            • Agile Consulting
            • Software Consulting
            • Data Analytics Consulting
            • CRM Consulting
          • Software Outsourcing
            • IT Staff Augmentation
            • Dedicated Development Teams
            • Shadow Engineers
            • Offshore Software Development
            • Offshore Development Center
            • White Label Services
          • Custom Software Development
            • Enterprise Software Development
            • Nearshore Software Development
          • Digital Transformation
    • Application Development
          • Mobile App Development
            • React Native App Development
            • iPhone app development
            • Android App Development
            • Flutter App Development
            • Cross Platform App Development
            • Xamarin App Development
          • Web Development
            • Website & Portal Development
          • Frontend Development
            • Angular Development
            • React.js Development
            • Next.js Development Services
          • Full Stack Development
            • MEAN Stack Development
            • MERN Stack Development
          • Backend Development
            • .NET Development
            • Node js Development
            • Laravel Development
            • PHP Development
            • Python Development
            • Java Development
            • WordPress Development
            • API Development
            • SharePoint Development
          • Cloud Application Development
            • Serverless Software Development
          • Application Maintenance
          • Application Modernization
    • QA & Testing
          • Penetration Testing
          • Usability Testing
          • Integration Testing
          • Security Testing
          • Automated Testing
          • Regression Testing
          • Vulnerability Assessment
          • Functional Testing
          • Software Performance Testing
          • QA Outsourcing
          • Web Application Testing
          • Software Quality Assurance Testers
          • Mobile App Testing
          • QA Consulting
          • Application Testing
    • eCommerce
          • eCommerce Web Design
          • Ecommerce Consulting
          • Digital Consulting
          • eCommerce Web Development
          • Supply Chain Automation
          • B2C eCommerce
          • B2B Ecommerce
    • Analytics & DevOps
          • Big Data Consulting
          • Business Intelligence Consulting
          • Microsoft Power BI
          • Power BI Implementation
          • DevOps Consulting
          • Amazon AWS
          • Microsoft Azure
    • Generative AI Development Services
          • Agentic AI Services
          • AI-ML Developers
          • Hire AI Developers
          • Machine Learning Developers
          • Deep Learning Development
          • IoT Developers
          • Chatbot Developers
  • Industries
    • Education & eLearning
    • Finance
    • Transportation & Logistics
    • Healthcare
      • Hospital Management Software Development
      • Patient Management Software Development
      • Clinic Management System
      • Telemedicine App Development Solutions
      • EMR Software
      • EHR Software
      • Laboratory Information Management Systems
    • Oil and Gas
    • Real Estate
    • Retail & E-commerce
    • Travel & Tourism
    • Media & Entertainment
    • Aviation
  • Hire Developers
    • Mobile Developers
          • Hire Android App Developers
          • Hire iOS App Developers
          • Hire Swift Developers
          • Hire Xamarin Developers
          • Hire React Native Developers
          • Hire Flutter Developers
          • Hire Ionic Developers
          • Hire Kotlin Developers
    • Web Developers
          • Hire .Net Developers
            • Hire ASP.NET Core Developers
          • Hire Java Developers
            • Hire Spring Boot Developers
          • Hire Python Developers
          • Hire Ruby On Rails Developers
          • Hire Php Developers
            • Hire Laravel Developers
            • Hire Codeigniter Developer
            • Hire WordPress Developers
            • Hire Yii Developers
            • Hire Zend Framework Developers
          • Hire Graphql Developers
    • Javascript Developers
          • Hire AngularJs Developers
          • Hire Node JS Developer
          • Hire ReactJS Developer
          • Hire VueJs Developers
    • Full Stack Developers
          • Hire MEAN Stack Developer
          • Hire MERN Stack Developer
    • Blockchain & Others
          • Hire Blockchain Developers
          • Hire Devops Engineers
          • Hire Golang Developers
  • Blogs
  • Careers
  • Company
    • Our Portfolio
    • About Us
    • Contact
  • Inquire Now
  • Menu Menu
Home1 / Backend2 / Binary search, its use cases, and complexities
Complexity Simplified with Binary Search

Binary search, its use cases, and complexities

April 4, 2022/1 Comment/in Backend /by Niki Savaliya

Quick Summary: Binary search, a robust algorithm, transforms search efficiency. An efficient method for locating a desired value in a sorted array involves repeatedly dividing the search area in half, with a logarithmic time complexity of O(log n). Its use cases include searching in large datasets and maintaining sorted collections. Read this blog to learn how Binary Search can advance your projects.

Introduction

The Binary Search algorithm is a very effective way to look for an item in a sorted list. It is a basic computer science tool for locating elements within a sorted collection. It does this by splitting the list repeatedly and searching the smaller half, therefore it can find the part.

This approach is, by a great margin, much better than the linear search approach that examines each element in the list individually. Binary search is quite versatile, being used in a great number of domains, from database management to information retrieval systems to sorting algorithms. Its time complexity is O(log n), which means that it’s pretty fast even for large datasets.

However, binary search is not without its complexities. Some of the listed complexities in binary search are handling duplicate elements or edge cases. An order-agnostic binary search would solve these challenges by allowing one to search within an array that is either sorted in an ascending or descending order.

Further, this write-up would present a discussion on binary search, its applications, and the complexities it is confronted with.

Further, it will bring out its importance in computer science and beyond.

So, read on.

What is binary search?

A Binary search element approach; A binary search algorithm divides a search interval in half repeatedly in a sorted array.

Binary search utilizes the fact that the array is sorted to reduce the time complexity to O(log n). Understand all four simple steps by a professional software service provider that are involved in the binary search:

To begin, cover the whole array with an interval.

In case the key value is less than the item centered in the interval, narrow it to the lower half.

  • To begin, cover the whole array with an interval.
  • In case the key value is less than the item centered in the interval, narrow it to the lower half.
  • If not, narrow it to the upper half.
  • Continue checking until you find the value or the interval is empty.

You can implement binary search in two ways or there are 2 algorithm for binary search

  • Iterative method
  • Recursive method

Iterative Algorithm:

Iterative algorithms continuously repeat a specific set of statements. It recounts the same steps continuously; an iterative algorithm uses looping statements such as for loops, while loops, and do-while loops.

Algorithm:

do until the pointers low and high meet each other.
            mid = (low + high)/2
            if (x == a[mid])
              return mid
        else if (x > a[mid]) // x is on the right side
              low = mid + 1
        else                // x is on the left side
              high = mid - 1

Recursive Algorithm:

As a recursive algorithm, a function calls itself until it reaches the stopping condition (base condition).

Let us track the search space by using two indexes start and end. Initially low = 0 and high = n – 1(as initially, the whole array is search space). At each step, we find a mid-value in the search space and compare it with the target value. There are three cases possible:

Case 1: If the target is equal to the middle, then return mid.

Case 2: If the target is less than the middle i.e target<A[mid], we discard all the elements in the right search space including the mid element. Now our new high would be mid-1 while ‘low’ remains as it is.

Case 3: If the target element is greater than the middle i.e target>A[mid], we discard all the elements in the left search space including the mid element. Now our new low would be mid+1 while ‘high’ remains as it is.

Algorithm:

binarySearch(arr, x, low, high)
            if low > high
                return False 
            else
                mid = (low + high) / 2 
                if x == a[mid]
                    return mid
                else if x > a[mid] // x is on the right side
                    return binarySearch(arr, x, mid + 1, high)
                else               // x is on the right side
                    return binarySearch(arr, x, low, mid - 1)

image1

1: Count the maximum number of positive and negative integers in an array

Assuming that the array a[] contains N integers, our task is to find the maximum among the counts of positive and negative integers in the array a[].

Example 1:

Input: a[] = {-19, -12, -7, -5, -1, 8, 12}

Output: 5

Explanation:

There are 2 positive numbers and 5 negative numbers. Among 5, 2 makes the maximum number: 5. Therefore, the output is 5.

Example 2:

Input: a[] = {-18, -11, 8, 14}

Output: 2

Explanation:

Here, the count of positive and negative numbers are the same which is why the output is 2.

Approach:

We can approach the given problem using Binary Search, the aim is to find the first index whose value is positive and print the maximum of both IDX and (N – IDX) as a result.

To solve the given problem, follow these steps:

  • We can initially define two variables, low as 0 and high as (N – 1).
  • Follow the below instructions to perform a Binary Search on the given array a[] by iterating until low <= high:
    • Calculate mid as (low + high) / 2.
    • If the value of mid is positive, then the right half shall be skipped by updating the high value to (mid – 1). Alternately, you may skip the left half by updating the value of low to (mid + 1).
  • As a result, compute the maximum of low and (N – low).

Implementation of the above approach using Python:

def getMax(a, length):
            low = 0
            high = length - 1
            while (low <= high):
              mid = low + (high - low) # 2 - Find the value of mid
                  if (a[mid] < 0): # If element is negative then, ignore the left half
                     low = mid + 1
                  elif (a[mid] > 0): # If element is positive then, ignore the right half
                      high = mid - 1
                  return max(low, length - low) # Return maximum among the count of positive & negative element
        if __name__ == "__main__":
            a = [-19, -12, -7, -5, -1, 8, 12]
            n = len(a)
            print(getMax(a, n))

Output:

5

3

Time Complexity: O(log N)
Space Complexity: O(1)

2: Order-Agnostic Binary Search

Order-Agnostic Binary Search is an upgraded version of the Binary Search algorithm. It features an additional condition checking capability. The algorithm’s reasoning is based on what would happen if an array was sorted without a specified order. Here, you must ensure that the value of the first element is greater or smaller than the value of the last element.

Case 1: If the first element is larger than the last element, then if the search key value X is smaller than the middle of the interval, the end pointer will be changed to mid -1, or else the start

the pointer will be changed to mid + 1.

Case 2: When the first element is greater than the last element, the start pointer will move to the next element in the middle element, if X is less than the middle of the interval, otherwise the end

the pointer will move before the middle element.

Ultimately, if the value of the search key matches the middle element, then the element is found for the search.

Let us see the implementation of Order-Agnostic Binary Search with the help of an example.

Given an array, a[] of size N and an element X, and the array is sorted in any order(ascending or descending), the task is to find whether element X is present in the array or not. If yes, then print its index, else print -1.

Example 1:

Input: a[] = {43, 27, 10, 6, 1}, N=5, X=6

Output: 3

Explanation:

The array is sorted in descending order and the element is present at index 1.

Example 2:

Input: a[] = {1}, N=1, X=10

Output: -1

Approach:

The brute force approach is about finding all possible solutions to a particular problem. So, the brute force approach would be to linearly traverse the array and check for the element. Using binary search would improve this algorithm if the sort order of the array was known – ascending/descending. Alternatively, an order-agnostic binary search can be used as follows:
You can solve this problem by using Order-Agnostic Binary Search by following the steps below:

  • As long as a[start] is less than a[end], initialize the boolean variable isAsc as true else as false.
  • Using a while loop, traverse a curve until the start is less than the end and take the following steps:
    • As a starting point, initialize the variable middle as the average of start and end.
    • The value of middle should be returned as the answer if a[middle] equals X.
    • Assuming that the array is sorted ascendingly, perform the following steps:
      • The value of start is middle+1 if a[middle] is less than X, and the value of end is middle-1 otherwise.
    • Otherwise, if a[middle] is less than X, set the value of end as middle-1 or set the value of start as middle+1.
  • If you perform the steps outlined above and no element is found, then return -1 as the answer.

Iterative implementation of Order-Agnostic Binary Search:

# Python program for the above approach using an iterative binary search.
        def binarySearch(a, start, end, x):
             isAsc = a[start] < a[end] # Checking the sorted order of the given array
             while (start <= end):
             middle = start + (end - start) // 2
             if (a[middle] == x): # Check if x is present at mid
            return middle
            if (isAsc == True): # Ascending order
            if (a[middle] < x): # If x greater, ignore left half
                 start = middle + 1
            else: # If x smaller, ignore right half
                 end = middle - 1
            else: # Descending order
            if (a[middle] > x): # If x smaller, ignore left half
                  start = middle + 1
              else: # If x greater, ignore right half
             end = middle - 1
               return -1 # Element is not present
        a = [ 60, 53, 35, 21, 17 ]
        x = 35
        n = len(a)
        print(binarySearch(a, 0, n - 1, x))

Output:

2

Time Complexity: O(log (N))
Space Complexity: O(1)

3: Identify the position of an element within an array of infinite numbers

When we see the array sorted, binary search immediately comes to mind, but there is a problem here since we don’t know how big the array is.

Due to the infinite nature of the array, there are no appropriate bounds to apply binary search. Therefore, to acquire the location of the key, we first determine the bounds and then run a binary search algorithm.

Example 1:

Input: a[] = {2, 5, 7, 9, 10, 12, 15, 16, 18, 20, 24, 28. 32, 35}, X = 16

Output: 7

Explanation:

The target is present at index ‘7’ in the array.

Example 2:

Input: a[] = {2, 5, 7, 9, 10, 12, 15, 16, 18, 20, 24, 28. 32, 35}, X = 19

Output: -1

Explanation:

The target is not present in the array.

Approach:

We can now compare the key with the high index element of the array by setting low to the 1st element and high to the 2nd element,

Case 1: When a key is greater than the high index element, duplicate the high index into the low index and double the high index.

Case 2: When smaller, apply a binary search between high and low indices found.

Implementation of the above approach using Python:

def binarySearch(a, left, right, x):
             if right >= left:
                  mid = left+(right-left)//2
                  if a[mid] == x:
                       return mid
                  if a[mid] > x:
                       return binarySearch(a, left, mid-1, x)
                  return binarySearch(a, mid+1, right, x)
        return -1
        
        def findPosition(a, key):
              left, right, val = 0, 1, a[0]
              while val < key:
                     left = right     #store previous high
                     right = 2*right  #double high index
                     val = a[right] #update new val
              return binarySearch(a, left, right, key)
        
        a = [3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170]
        ans = findPosition(a, 90)
        if ans == -1:
               print ("An element not found in list.")
        else:
               print("An element found at index ",ans)

Output:

An element found at index 5

Time Complexity: O(log P), where p is the position of the element to be searched.

Space Complexity: O(1)

4: Find the Kth smallest element in a 2D array that is sorted row-wise and column-wise

It pretty much takes care of itself when we speak of the Kth Smallest Element in a Sorted Matrix.

Therefore, we must find a number greater than or equal to exactly the K-1 elements of our matrix.

Matrixes can also be analyzed with Binary Search, but this is different from a conventional binary search because, instead of using the “index range”, we consider the “number range”(matrix values themselves). Generally speaking, we know that the smallest number in our matrix is at the top left corner and the biggest number is at the bottom lower corner. As a result, these two numbers can represent the Binary Search’s “range”, i.e., the values that are high and low.

Example:

matrix =

15, 25, 31, 43
16, 27, 36, 45
28, 30, 39, 49
33, 35, 40, 50

low=15 and high=50

Steps:

Iteration low high mid count Explanation
1 15 50 32 7 count is not lesser than 3 => high = mid
2 15 32 23 2 count is lesser than 3 => low = mid + 1
3 24 32 28 5 count is not lesser than 3 => high = mid
4 24 28 26 3 count is not lesser than 3 => high = mid
5 24 26 25 3 count is not lesser than 3 => high = mid
6 24 25 24 2 count is lesser than 3 => low = mid + 1
7 25 25 low is not lesser than mid, the loop terminates

Approach:

  • To begin the Binary Search, set low = matrix[0][0] and high = matrix[n-1][n-1].
  • Calculate the midpoint of the low and the high. Note that this number is not necessarily part of the matrices.
  • In the matrix, count all numbers smaller than or equal to mid. Since the matrix is sorted, this can be done in O(N).
  • In the case where the count is less than ‘K’, we can set low = mid+1 to search the higher part of the matrix.
  • Otherwise, if the count is equal to or greater than ‘K’, we can update high = mid to search in the lower part of the matrix in the next iteration.
  • After a certain point, the low and high values become equal, and the loop ends. We narrowed down the search range to one matrix element iteratively by collecting the value of the Kth smallest element.

Implementation of the above approach using Python:

# This returns count of elements in matrix less than or equal to num
        def searchElementGreaterThanOrEqual(num, n, mat): 
             ans = 0
             for i in range(0,n):
                   # if num is less than the first element then no more element in matrix further are less than or equal to num
             if (mat[i][0] > num):
                 return ans
                  # if num is greater than last element, it is greater than all elements in that row
                if (mat[i][n - 1] <= num):
                    ans += n
                    continue
                   # This contain the col index of last element in matrix less than of equal to num
                 greaterThan = 0
                 jump = n//2
                 while (jump >= 1):
                     while (greaterThan + jump < n and mat[i][greaterThan + jump] <= num):
                          greaterThan += jump
                    jump = jump // 2
                 ans += greaterThan + 1
             return ans
        
        # returns kth smallest index in the matrix
             def kthSmallest(matrix, n, k):
                l = matrix[0][0]
                r = matrix[n-1][n-1]
                while (l <= r):
                 mid = l + (r - l) // 2
                       greaterThanOrEqualMid = searchElementGreaterThanOrEqual(mid, n, matrix)
                 if (greaterThanOrEqualMid >= k):
                   r = mid - 1;
                 else:
                    l = mid + 1;
                 return l;
        a =[[15,25,31,43],
           [16,27,36,45],
           [28,30,39,49], 
           [33,35,40,50]]
        print("3rd smallest element in matrix is " + str(kthSmallest(a, 4, 3)))

Output:

3rd smallest element in the matrix is 25

Time Complexity: O(N)
Space Complexity: O(1)

Conclusion

As a result of using the four approaches discussed in this post, I have solved a lot of coding problems and have been able to effectively use binary search with other data structures, like matrices and lists.

Additionally, to harness the Binary search, take help Bigscal. Here at Bigscal, we adept a team of skilled professionals. Our team can transform complex challenges into manageable solutions.

So, be daring at all times. It will pay off! Thanks for reading, and happy programming!

If you have any doubts or suggestions, feel free to commen

FAQ

What are the complexities of binary search?

The binary search algorithm finds an element in a sorted array highly efficiently. Its time complexity equals O(log n), where n denotes the number of factors since it has the search space with each step. However, using it requires a sorted array and cannot be used on unsorted data. Furthermore, performing insertion and deletion operations can be complex, as maintaining the sorted order after modifications may involve shifting elements.

What are the average case complexities of a binary search?

Binary search has an average-case complexity of O(log n), where n represents the number of elements. This assumption is based on eliminating roughly half of the remaining search space with each comparison. Dividing the search space in half with each step means the number of steps needed to find an element increases logarithmically as the input size grows. This efficiency makes binary search a popular option for searching large sorted datasets.

What is the use case of binary search?

People often use binary search to quickly retrieve data from large sorted datasets, such as phone directories, dictionaries, or sorted databases. Binary search is also helpful in algorithms like binary search trees for efficient data storage and retrieval. However, binary search does not work well with unsorted data or dynamic data structures because it requires a sorted array and does not adapt well to frequent insertions or deletions.

How to reduce complexity of binary search?

To decrease binary search complexity:

  • Focus on efficient comparisons.
  • Eliminate redundant checks and optimize midpoint calculations.
  • Try variations like ternary or interpolation search for specific datasets—Preprocess data by caching or auxiliary structures.
  • Implement early exit conditions when the target is impossible within the range.
  • For dynamic data, use balanced structures like AVL trees.
  • Tailor strategies to data characteristics and problem requirements for an optimized search process.

Why is binary search space complexity?

Binary search has a space complexity of O(1), which means it uses a constant amount of additional memory regardless of the input data size. It is because binary search operates using a recursive or iterative approach, maintaining only a few variables to track the search range and the midpoint. It doesn’t require additional data structures that grow with the input size. As a result, the space complexity remains constant, making binary search highly memory-efficient for finding elements in sorted datasets.

Tags: #algorithm, #array, #bigscal, #bigscal Technologies, #binary, #complexity, #element, #hire dedicated developers, #matrix, #search, #technologies

You might also like

Stripe+React Native: Your E-Commerce Solution How to Integrate Stripe Payment Gateway in React Native
Why-Li-fi-Is-Better-Than-Wi-fi Why Li-fi Is Better Than Wi-fi?
React Native FAQs: 2022 Edition Important Frequently Ask Questions (FAQs) about React Native in 2022
Master SQL with Top 10 Performance Boosting Tips Top 10 Tips to Improve SQL Query Performance
Log With Serilog In .Net 6.0 Log with Serilog in .net 6.0
Optimize React for Maximum Efficiency! Methods of How to Improving and Optimizing Performance in React Application

Seeking robust and scalable software solutions?

Contact us for industry-leading development services.

Book a 30 min FREE Call

Craft your Best Agile Team

Your Project, Our Expertise - Hire a Developer Now

    Subscribe for
    weekly updates

      privacy-policy I accept the terms and conditions

      Categories

      • AI-ML-Blockchain
      • Aviation
      • Backend
      • Cloud
      • Cross Platform
      • Cyber Security
      • Database
      • DevOps
      • Digital Marketing
      • Ecommerce
      • Education Industry
      • Entertainment Industry
      • Fintech Industries
      • Frontend
      • Full Stack
      • Game Development
      • Healthcare Industry
      • Latest Technology News
      • Logistics Industry
      • Mobile app development
      • Oil And Gas Industry
      • Plugins and Extensions
      • QA & Testing
      • Real Estate Industry
      • SaaS
      • Software Development
      • Top and best Company
      • Travel industries
      • UI UX
      • Website Development

      Table of Content

      bigscal-technology
      india
      1st Floor, B - Millenium Point,
      Opp. Gabani Kidney Hospital,
      Lal Darwaja Station Rd,
      Surat – 395003, Gujarat, INDIA.
      us
      1915, 447 Broadway,
      2nd Floor, New York,
      US, 10013
      +91 7862861254
      [email protected]

      • About
      • Career
      • Blog
      • Terms & Conditions
      • Privacy Policy
      • Sitemap
      • Contact Us
      Google reviews
      DMCA.com Protection Status
      GoodFirms Badge
      clutch-widget
      © Copyright - Bigscal - Software Development Company
      Google reviews
      DMCA.com Protection Status
      GoodFirms Badge
      clutch-widget

      Stay With Us

      Are you looking for the perfect partner for your next software project?

      Google reviews GoodFirms Badge clutch-widget
      • IP Rights, Security & NDA. Full ownership and confidentiality with robust security guaranteed.
      • Flexible Contracts & Transparency. Tailored contracts with clear and flexible processes.
      • Free Trial & Quick Setup. No-risk trial and swift onboarding process.

        How Statistics is used in Machine Learning? Decode the Role of Statistics in Machine Learning! Power Up your Business with the Tableau BI tool Tableau – A Powerful BI Tool
        Scroll to top

        We use cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.

        AcceptHide notification onlySettings

        Cookie and Privacy Settings



        How we use cookies

        We may request cookies to be set on your device. We use cookies to let us know when you visit our websites, how you interact with us, to enrich your user experience, and to customize your relationship with our website.

        Click on the different category headings to find out more. You can also change some of your preferences. Note that blocking some types of cookies may impact your experience on our websites and the services we are able to offer.

        Essential Website Cookies

        These cookies are strictly necessary to provide you with services available through our website and to use some of its features.

        Because these cookies are strictly necessary to deliver the website, refuseing them will have impact how our site functions. You always can block or delete cookies by changing your browser settings and force blocking all cookies on this website. But this will always prompt you to accept/refuse cookies when revisiting our site.

        We fully respect if you want to refuse cookies but to avoid asking you again and again kindly allow us to store a cookie for that. You are free to opt out any time or opt in for other cookies to get a better experience. If you refuse cookies we will remove all set cookies in our domain.

        We provide you with a list of stored cookies on your computer in our domain so you can check what we stored. Due to security reasons we are not able to show or modify cookies from other domains. You can check these in your browser security settings.

        Other external services

        We also use different external services like Google Webfonts, Google Maps, and external Video providers. Since these providers may collect personal data like your IP address we allow you to block them here. Please be aware that this might heavily reduce the functionality and appearance of our site. Changes will take effect once you reload the page.

        Google Webfont Settings:

        Google Map Settings:

        Google reCaptcha Settings:

        Vimeo and Youtube video embeds:

        Privacy Policy

        You can read about our cookies and privacy settings in detail on our Privacy Policy Page.

        Privacy Policy
        Accept settingsHide notification only