Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you’ve narrowed down the possible locations to just one.
One of the most common ways to use binary search is to find an item in an array. For example, the Tycho-2 star catalog contains information about the brightest 2,539,913 stars in our galaxy. Suppose that you want to search the catalog for a particular star, based on the star’s name. If the program examined every star in the star catalog in order starting with the first, an algorithm called linear search, the computer might have to examine all 2,539,913 stars to find the star you were looking for, in the worst case. If the catalog were sorted alphabetically by star names, the binary search would not have to examine more than 22 stars, even in the worst case.
Also, read about the JAVA complete information by going through this article.
The next few articles discuss how to describe the algorithm carefully, how to implement the algorithm in JavaScript, and how to analyze efficiency.
Describing binary search
When describing an algorithm to a fellow human being, an incomplete description is often good enough. Some details may be left out of a recipe for a cake; the recipe assumes that you know how to open the refrigerator to get the eggs out and that you know how to crack the eggs. People might intuitively know how to fill in the missing details, but computer programs do not. That’s why we need to describe computer algorithms completely.
Must read about C# to give a good start to your career.
To implement an algorithm in a programming language, you will need to understand an algorithm down to the details. What are the inputs to the problem? The outputs? What variables should be created, and what initial values should they have? What intermediate steps should be taken to compute other values and ultimately compute the output? Do these steps repeat instructions that can be written in simplified form using a loop?
Binary Search in Array
Let’s see how to think about binary search on a sorted array. Yes, JavaScript already provides methods for determining whether a given element is in an array and, if it is, its location (as do many programming languages), but we want to implement it ourselves, to understand how you can implement such methods. Here’s a JavaScript array of the first 25 prime numbers, in order. You can join the Bootcamp coding courses at Edureify by visiting the official website.
Example:- var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
Solution:- Suppose we want to know whether the number 67 is prime. If 67 is in the array, then it’s prime.
We might also want to know how many primes are smaller than 67. If we find the position of the number 67 in the array, we can use that to figure out how many smaller primes exist.
The position of an element in an array is known as its index. Array indices start at 0 and count upwards. If an element is at index 0 then it is the first element in the array. If an element is at index 3, then it has 3 elements that come before it in the array.
Looking at the example, we can read the array of prime numbers from left to right, one at a time, until we find the number 67 (in the pink box) and see that it is at array index 18. Looking through the numbers in order like this is a linear search.
Once we know that the prime number 67 is at index 18, we can identify that it is a prime. We can also quickly identify that 18 elements come before 67 in the array, meaning that there are 18 prime numbers smaller than 67. Read about various Bootcamp coding courses such as JAVA, python, etc at Edureify.
Frequently Asked Questions (FAQs)
Question:- What is meant by binary search?
Answer:- Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you’ve narrowed down the possible locations to just one. We used binary search in the guessing game in the introductory tutorial.
Question:- What is binary search in C?
Answer:- A Binary Search is a sorting algorithm that is used to search an element in a sorted array. A binary search technique works only on a sorted array, so an array must be sorted to apply binary search on the array.
Question:- What are binary search and linear search?
Answer:- Linear search is a search that finds an element in the list by searching the element sequentially until the element is found in the list. On the other hand, a binary search is a search that finds the middle element in the list recursively until the middle element is matched with a searched element. Read about the various coding courses offered at Edureify and get ready to be enrolled in one of the most informational courses related to coding.
Question:- What is the advantage of binary search?
Answer:- One of the main advantages of a binary search is that it is much quicker than a serial search because the data that needs to be searched halves with each step. For example, it is possible to search through 1024 values and find the one you want within 10 steps, every time.
Question:- What is the algorithm used for binary search?
Answer:- Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.
