Scribd
Upload
2 views36 pages

Optimizing Bubble and Binary Search

The document discusses optimized implementations of bubble sort and various searching techniques, including linear and binary search. It highlights the efficiency of binary search by eliminating large portions of the search space, and explains the time complexities associated with these algorithms. Additionally, it touches on the concept of finding the floor of a number and calculating the frequency of an element in an array using binary search.

Uploaded by

sandykeilber123
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views36 pages

Optimizing Bubble and Binary Search

The document discusses optimized implementations of bubble sort and various searching techniques, including linear and binary search. It highlights the efficiency of binary search by eliminating large portions of the search space, and explains the time complexities associated with these algorithms. Additionally, it touches on the concept of finding the floor of a number and calculating the frequency of an element in an array using binary search.

Uploaded by

sandykeilber123
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

NOTEBOOK

Optimized Implementation of Bubble Sort:


• The above function always runs O(n^2) time even if the array is sorted.
• It can be optimized by stopping the algorithm if the inner loop didn’t cause any swap.
Searching
Suppose I need to find book-6 :-
Take each book This is cumbersome method to find the book, now if we arrange it
Inspect in alphabetical order searching is faster and easier.
Take next book

if there is a pattern / ordering let's exploit & search faster.

1. Guessing game 1 1. Guessing game 2 (Too high or too low)


IDEA OF LINEAR SEARCH IDEA OF BINARY SEARCH :- In this case we find the number faster than last time
Strategy :- be cause we are eliminating large chunk of space.
A. Random in (1, 1000) Strategy:-
B. Guess in increasing order A. Initial search space [1,1000] .
B. Guess a random x in the range
C. If the guess is too high answer lies here [ 1, x-1]
D. If the guess is too low answer lies here [ x+1, 1000]

If by making a guess we are able to eliminate a large portion of answers then we can search faster.
Why a random guess in the range ?

In best case 70% search space discarded i.e. I.E (30% space we all able to find that no)
In worst case 30% search space will discard I.e. We have to find that number in 70% space which is tough

If we divide it into middle


Our main objective is to discard
In best case 50% search space discarded
maximum search space
In worst case 50% search space discarded
Binary search

Low High Mid Arr[mid] Action


Now let's tale element = 13

Low High Mid Arr[mid] Action

So 13 is not in the array so it should return -1.


We divide search space into two
halves . so time complexity of searching
in whole search space is nothing but
searching in half space
Iterative approach.
Why divide array into 2 parts

Finl iteration =
Dividing array into 3 part
Iteration * no of comparison In every iteration , 67% of search space
got discarded

Dividing array into 4 part


In every iteration, 75% of search space
got discarded

Dividing array into n part


If you are dividing into more than 2 parts time complexity is increasing. That's
why dividing into 2 pasts is best option
Q: - floor of a number. Note: - floor of x is largest element in the array smaller than equal to x

Answer:- max [ arr[i] =< x]

Brute Force
To find:- max ( arr[i] < 12)
Binary search.
Q :- Search the array and find the frequency of that element

Frequency of 5 = P2 - P1 +1

TC :- O(log N ) + O(N)
In worst case we have to
go entire left side and
Due to which
entire right side( travelling
we are able to
the entire array will
land 5
require O(N) time
complexity.

You might also like