An algorithm (pronounced AL-go-rith-um) is a procedure or formula for solving a problem, based on conducting a sequence of specified actions. A computer program can be viewed as an elaborate algorithm.Step by step procedure designed to perform an operation, and which will lead to the sought result if followed correctly. Algorithms have a definite beginning and a definite end, and a finite number of steps. An algorithm produces the same output information given the same input information, and several short algorithms can be combined to perform complex tasks such as writing a computer program. A cookbook recipe, a diagnosis, a problem solving routine, are some common examples of simple algorithms. Suitable for solving structured problems (amenable to sequential analysis) algorithms are, however, unsuitable for problems where value judgments are required.
The characteristics of a good algorithm are:
Precision – the steps are precisely stated(defined).
Uniqueness – results of each step are uniquely definedand only depend on the input and the result of the precedingsteps.
Finiteness – the algorithm stops after a finite number ofinstructions are executed.
Elements of Algorithms:
- Acquire data (input) some means of reading values from an external source; most algorithms require data values to define the specific problem (e.g., coefficients of a polynomial).
- Computation some means of performing arithmetic.computations, comparisons, testing logical conditions.
- Selection some means of choosing among two or more possible courses of action, based upon initial data, user input and/or computed results.
- Iteration some means of repeatedly executing a collection of instructions, for a fixed number of times or until some logical condition holds .
- Report results (output) some means of reporting computed results to the user, or requesting additional data from the user.
Algorithm is quite simple. It can be done either recursively or iteratively:
- Get the middle element;
- If the middle element equals to the searched value, the algorithm stops;otherwise, two cases are possible:
- Searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element. Searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.
Searching is the process of finding a given value position in a list of values. It decides whether a search key is present in the data or not. It is the algorithmic process of finding a particular item in a collection of items. It can be done on internal data structure or on external data structure.Searching algorithm can be used to help find the item of data you are looking for.A search algorithm is the step-by-step procedure used to locate specific data among a collection of data. It is considered a fundamental procedure in computing. In computer science, when searching for data, the difference between a fast application and a slower one often lies in the use of the proper search algorithm.
Searching Algorithms :
- Linear Search.
- Binary Search.
- Jump Search.
- Interpolation Search.
- Exponential Search.
- Sublist Search (Search a linked list in another list)
- Fibonacci Search.
- The Ubiquitous Binary Search.
Binary Search Algorithm:
Binary search is a fast search algorithm with run-time complexity of Οlogn. This search algorithm works on the principle of divide and conquer. For this algorithm to work properly the data collection should be in sorted form. Binary search search a particular item by comparing the middle most item of the collection. If match occurs then index of item is returned. If middle item is greater than item then item is searched in sub-array to the right of the middle item other wise item is search in sub-array to the left of the middle item. This process continues on sub-array as well until the size of subarray reduces to zero. Binary search works on sorted arrays. Binary search begins by comparing the middle element of the array with the target value.
Binary Search Algorithm:
- Start with the middle element: If the target value is equal to the middle element of the array, then return the index of the middle element. If not, then compare the middle element with the target value, ...
- When a match is found, return the index of the element matched.
- If no match is found, then return -1.
Binary search, also known as half-interval search,logarithmic search,or binary chop, is a search agorithm that finds the position of a target value within a sorted array.Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. Even though the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation, particularly if the values in the array are not all of the whole numbers in the range.
There is a good run-down of the pre-conditions of binary search here: The array must be sorted in ascending order according to the ordering used by the comparisons in the search function. The author only specifies one pre-condition but I expect you could break it down to 2 conditions that are related to each other.Binary search is a widely used searching algorithm that requires the array to be sorted before search is applied. The main idea behind this algorithm is to keep dividing the array in half (divide and conquer) until the element is found, or all the elements are exhausted.
Binary search is more efficient than linear search; it has a time complexity of O(log n). The list of data must be in a sorted order for it to work. A binary searchworks by finding the middle element of a sorted array and comparing it to your target element.In general, if N is the size of the list to be searched and C is the number of comparisons to do so in the worst case, C = log2N. Thus, the efficiency of binary search can be expressed as a logarithmic function, in which the number of comparisons required to find a target increases logarithmically with the size.Binary Search Algorithm. Binary Search is applied on the sorted array or list of large size. It's time complexity of O(log n) makes it very fast as compared to other sorting algorithms.
Advantages of Binary Search:
- Compared to linear search (checking each element in the array starting from the first), binary search is much faster. Linear search takes, on average N/2 comparisons (where N is the number of elements in the array), and worst case N comparisons. Binary search takes an average and worst-case log2(N)log2(N)comparisons. So for a million elements, linear search would take an average of 500,000 comparisons, whereas binary search would take 20.
- It’s a fairly simple algorithm, though people get it wrong all the time.
- It’s well known and often implemented for you as a library routine.
Disadvantages of Binary Search:
- It’s more complicated than linear search, and is overkill for very small numbers of elements.
- It works only on lists that are sorted and kept sorted. That is not always feasable, especially if elements are constantly being added to the list.
- It works only on element types for which there exists a less-than relationship. Some types simply cannot be sorted (though this is rare).
- There is a great lost of efficiency if the list does not support random-access. You need, for example, to immediately jump to the middle of the list. If your list is a plain array, that’s great. If it’s a linked-list, not so much. Depending on the cost of your comparison operation, the cost of traversing a non-random-access list could dwarf the cost of the comparisons.
- There are even faster search methods available, such as hash lookups. However a hash lookup requires the elements to be organized in a much more complicated data structure (a hash table, not a list).
Binary search is one of the most common search algorithms and is useful in most any real world application you might write. Binary search is a more specialized algorithm than sequential search as it takes advantage of data that has been sorted. The underlying idea of binary search is to divide the sorted data into two halves and to examine the data at the point of the split. In this research paper you came to know about the algoritm of binary search and how binary search is more appreciable than any other search.It also explain that which language support binary algorithm.