Skip to main content

Featured Post

Top 10 Advance Java Interview questions?

Top 10 Advance Java Interview questions?   What are the differences between abstract classes and interfaces in Java? What is the difference between ArrayList and LinkedList in Java? What is the purpose of the finalize() method in Java? What is polymorphism in Java and how is it achieved? What are the different types of inner classes in Java? What is the difference between static and non-static methods in Java? What are the different types of exceptions in Java and how do they differ? What is the difference between checked and unchecked exceptions in Java? How does Java handle multithreading and synchronization? What are the different types of JDBC drivers in Java and how do they differ?
Post a Comment

Binary Search in Data Structure

 

Binary Search in Data Structure


There are various ways to search a particular element from a given list. One of them is Binary search.
When there exists so much data everywhere, it is very necessary to have a good searching method to search for the particular data in lesser time.

Binary search works faster than linear search. It is one of the fastest searching algorithms.

What is Binary Search?

It is a searching technique. It is based upon Divide and conquer strategy. Binary search is applicable only on sorted data. It takes O(log n) time for completion.

It divides the given array into halves and then checks the middle element. If the middle element is smaller than the element to be searched, the algorithm selects the second half of the array and discards the first half.

Thus, at every step, the binary search algorithm keeps on discarding half of the array based on the value of the middle element. This process continues until the array becomes of the size 1 or 2 and the algorithm finally gets the required element.

If the search is successful i.e. the element is present in the array, it returns the index of that element. If the element is not present inside the array, the algorithm returns -1.

Working of Binary Search


Suppose we wish to search 38 in the array.

Step 1: Find the middle element of the array.

index(Middle) = index(low) + index(high – low)/2.

Here, middle = 0 + (9-0)/2 = 4 i.e. the element at the 4th index i.e. 25.



Step 2: Compare 38 with the middle element. 38 > 25 So, discard the first half.

Step 3: Select the send half of the array. For the second half, low = middle+1 as shown:




Step 4: Find the middle element of this smaller array which comes out to 32. Compare 38 with 32.


38 > 32 Thus, discard the first half of this array.

Step 5: Select the remaining half of the array by doing low = middle+1 as shown:



Finally, we have found 38 and thus the algorithm will halt here.

Output:  8.



Labels:

Comments

Post a Comment

Popular posts from this blog

WHAT ARE NEURAL NETWORKS? | Comingfly

WHAT ARE NEURAL NETWORKS ? Neural Networks the process of machine learning are neural networks. These are brain-inspired networks of interconnected layers of algorithms, called neurons, that feed data into each other, and which can be trained to carry out specific tasks by modifying the importance attributed to input data as it passes between the layers. During training of these neural networks, the weights attached to different inputs will continue to be varied until the output from the neural network is very close to what is desired, at which point the network will have 'learned' how to carry out a particular task. A subset of machine learning is deep learning, where neural networks are expanded into sprawling networks with a huge number of layers that are trained using massive amounts of data. It is these deep neural networks that have fueled the current leap forward in the ability of computers to carry out task like speech recognition and computer vision. T here are vario...
6 comments
Read more

What is Go Language ? | Comingfly

What is Go Language ? What Go Language? :- v    Go is a modern, general purpose language. v    A new ,Open source Programming language. v    Concurrent , Builds fast at scale. v    Go language is very fast. v    Garbage-Collected. v    Lightweight syntax. v    Simple type system. v    Productive. v    Simple. v    Fun History of Go language :- Go language developed by Rob Pike   and Ken Thompson. More than 250 contributors join the project.   Design began late in 2007.   Become open source in 2009.   Version is 1.2.2. Feature of Go language ? v   In the current world, languages don't help enough. v   Computers fast but software construction slow. v   Efficiency. v   Safety. v   Speed. v   Concurrency. v   Scalability. v   Fast development cycle. v   No surprises. v   Multi-core Why Developed a Language ? Google has bi...
5 comments
Read more

What is Java? | Comingfly

What is Java? Developed by Sun Microsystems in the mid-1990s, Java was originally built to be a high-level and object-oriented programming language that looks and feels similar to C++. Along with being extremely popular, Java can implement a wide variety of algorithms, which are very useful to the machine learning community. Java is regarded as one of the most secure programming languages, largely due to its use of bytecode and sandboxes. Java manages to harness much of the power of C++ while overcoming its security issues and overall complexity. But with all of its improvements over C++, Java has a reputation for being slower than many other programming languages. Additionally, as of 2019, Java has implemented commercial licensing for certain business applications, which can be costly.
Post a Comment
Read more