Binary Search

 Problem: We have a sorted array and a key element, we need to find out if the key element is present in the array. If it exists return the index of that element or return -1 if it doesn't exist. If the array has repeated elements, the order of the index is not important.

Example:




Pseudocode:
Step 1: Initialise low = 0, high = array.count - 1
Step 2: Run a loop until low <= high
Step 3: Compute middle index
           middle  = (low + high) / 2
Step 4: If array[middle] == x, we found the index, then
           return x
Step 5: If  x < array[middle], x lies in the first half of the array, then
           high = middle - 1
           repeat from step 2
Step 6: If x > array[middle], x lies in the second half of the array, then
           low = middle + 1
           repeat from step 2
Step 7: return -1, as x is not present in the array

Iterative Binary Search:  
    

func binarySearch(array:[Int],x:Int,n:Int)->Int{
    var low = 0, high = n
    

    while low <= high {
        let mid = (low + high) / 2
        
        if array[mid] == x{
            return mid
        }else if x < array[mid]{
            high = mid - 1
        }else{
            low = mid + 1
        }
   }
    return -1
}

Recursive Binary Search:  


func binarySearch(array:[Int],x:Int,low:Int,high:Int)->Int{
    if low > high {
        return -1
    }
    

    let mid = (low + high) / 2
    
    if array[mid] == x{
        return mid
    }else if x < array[mid]{
        return binarySearch(array: array, x: x, low: low, high: mid - 1)
    }
    return binarySearch(array: array, x: x, low: mid + 1, high: high)
}

Time Complexity of Iterative Binary Search
Let's say the iteration in Binary Search terminates after k iterations. 
At each iteration, the array is divided by half.
Length of array = n 

Iteration 1: Length of array = n
Iteration 2: Length of array = n / 2 
Iteration 3: Length of array = (n / 2) / 2 = n / 2²  
.
.
.
Iteration k: Length of array = n / 2k   

We can not divide the array further because at Iteration k, array contains only one element.
so at,

Iteration k: length of array = 1 = n / 2k   
=> 1 = n / 2k   
  => n = 2k 

Applying log function on both sides
  => log2 (n)  = log2 (2k) 
  => log2 (n)  = log2 (2k) 
  => log2 (n)  = k log2 (2)    
  => log2 (n)  = k    ∵   log2 (2) = 1
∴ k  = log2 (n)  

Hence Time complexity of Binary search = log2 (n)  

Space Complexity of Iterative Binary Search:
 O(1) for maintaining function call stack 



Time Complexity of Recursive Binary Search
Recurrence Relation:
At each recursion, array is being divided by half.
i.e. n => n/2 => n/4 => n/8......
Since we are interested in only one recursion we'll consider

T(n) = T(n/2) + c where c is conditions or mid calculation..


T(n) =    T(n/2)+c   if  n > 1
1     if  n = 1 

Time Complexity using Substitution method:
Step 1:  T(n)     =  T(n/2) + c
Step 2:  T(n/2)  =  T(n/4) + c
Step 3:  T(n/4)  =  T(n/8) + c

Substitute T(n/2) in Step-1

=> T(n) = T(n/4) + c + c  = T(n/2²) + 2c

Substitute T(n/4) in above
=> T(n) = T(n/8) + c + 2c  = T(n/23) + 3c
=>       = T(n/24) + 4c
=>       = T(n/25) + 5c
.
.
.
at kth step
=>        T(n)  = T(n/2k) + kc
.
.
.
Recursive call will stop when length of array = 1 => n = 1 =>  T(1) = 1

In the above equation, to get T(1) we'll consider n = 2k

=>       T(n) = T(2k /  2k ) + kc
=>       T(n) = T(1) + kc
=>       T(n) = 1 + kc

Since n = 2k, take log on both sides
=>       log2 n = k log2 2
=>       k = log2 n

∴ Substitute k in above equation
=>       T(n) = 1 +  log2 n * c
=>       T(n) = log2 n 

So Time complexity is O(log n)

Space Complexity of Recursive Binary Search : 
O(log n) for maintaing function call stack 

Comments

Post a Comment

Popular posts from this blog

Swift Package Manager: Demystifying Targets and Libraries

Target vs Library If you'v dabbled with Swift Package Manager (SwiftPM), you've likely encountered targets and libraries in a Package.swift file and wondered what sets them apart. These concepts are essential to structuring your code effectively, especially as projects grow larger. In this post, we'll break down the difference between the two, explore how they're used, and walk through real-world examples that show how you can build scalable and modular Swift packages. What Exactly Is a Target? In SwiftPM, a target is the fundamental unit of code compilation. It's basically a module that consists of source files, dependencies, and optionally resources or tests. Targets are used internally within your package. For example: .target(name: "Logger") This line defines a module named Logger . You can import and use this module from other targets inside your package. And a Library? A library is a product. It’s what you offer to the outside world—other packag...
Read more

IOS Simulator Crash report

If your iOS app crashes in the Simulator during a test run, the crash report can be used for diagnosing the exact cause of the crash. By default, the crash reports for the app will be written to the ~/Library/Logs/DiagnosticReports directory. The crash reports can be uploaded as artifacts to assist with debugging the app crash on your local machine: - store_artifacts: path: ~/Library/Logs/DiagnosticReports
Read more

Palindrome check

A Palindrome is a word, phrase, or sequence that reads the same backward as forward. Ex: RaceCar, madam, mom, level We have two methods to check for a palindrome. 1. Reverse String Comparision: If we reverse a string and compare it with the given string, then if both the strings are equal, we can say the given string is a palindrome. func reversedString(input: String )-> String { var reversed = "" for char in input{ reversed = "\(char)" + reversed } return reversed } func isPalindrome( _ input : String )-> Bool { let reversed = reversedString (input: input) return reversed == input } Time Complexity: θ(n) Space Complexity: θ(n) 2. Character Comparision: We'll start comparing the first character with the last character, if both are equal we'll increment the left index & decrement the right index until we cross the middle character. If we successfully pass the middle character then the given s...
Read more