Skip to main content

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
   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

Popular posts from this blog

UILabel text animation as in UIButton click

Animating UILabel textcolor is not easy as it seems, normal animation won't work on this property. The below code snippet animates the UILabel textcolor as in button click. Change the duration and UIViewAnimationOptions to play with it. extension UILabel { func flashLabel() { func animate(duration: Double ,alpha: CGFloat ,completion:(()->())?){ UIView . transition (with: self , duration: duration, options: UIViewAnimationOptions . transitionCrossDissolve , animations: { self . textColor = self . textColor ?. withAlphaComponent (alpha) }) { _ in completion?() } } animate (duration: 0.1 , alpha: 0 ) { animate (duration: 0.3 , alpha: 1 , completion: nil ) } } } Happy coding...

Confused OS Concepts

Difference between MultiProcessor and Multicore Processor? A  multiprocessor   system  contains more than one CPU, allowing them to work in parallel. A  multicore   CPU  has multiple execution cores on one CPU so that multiple cores can work in parallel on separate operations at chip level. Difference between MultiProgramming, MultiTasking, MultiProcessing,      MultiThreading? MultiProgramming: To minimize the CPU Idle time, Multiprogramming was introduced in older days for single core processor. One or more programs are loaded into main memory which are ready to execute still, only one program is able to get the CPU for execution while all others are waiting for their turn. When currently running process is performing an I/O task, then OS may interrupt that process and give the control to another program( process context switching ) loaded in main memory for execution and a running process keeps executing until either it voluntarily releases the CPU or when it blocks for an I

Design Patterns in Swift

What is a Design pattern? A design pattern is a general solution to a real-world problem that can be re-used. Design patterns are formalized best practices that the programmer can use to solve common problems when designing an application or system. They are templates designed to help us write efficient code which is easy to understand, also can be re-used. It is not a finished design that can be transformed directly into source or machine code. Why do we need Design patterns? Saves Time : Design patterns can speed up the development process by providing tested, proven development paradigms Future bugs : Effective design pattern can solve issues that may not become visible until later in the implementation, which helps while designing software. Re-use : Reusing design patterns helps to prevent subtle issues that can cause major problems. Code Readability : Improves code readability for coders and architects familiar with the patterns. Best practices : Design patterns teaches