Binary search adds a small bit of overhead for a large performance gain. The basic input for binary search is that the collection is kept in a sorted manner before the search happens. A telephone book is the best example for a large scale binary search.
The concept of binary search is simple: In a sorted list where each element supports comparability, search for the target element in the middle. If the target value is less, discard the right half of the list and if the target is more, discard the left half. Continue this process with the remaining half till the element is found or the search element does not exist.
Linear search is a brute force approach. Binary search is more in the category of Divide and conquer. The best case performance is same as linear search: O(1). But the average and worst case performance actually becomes O(log n) which is exponentially better than linear search. Consider this: Binary search divides the the size of the problem in half every iteration.
Now let's look at one possible solution. In this example, I would like to introduce to you 3 advanced concepts from the .NET world: Generics, Generic constraints and the IComparable<T> interface. Any object implementing the IComparable interface guarantees that it's elements will be comparable to each other in a meaningful way. Let's look at the code now:
using System;
namespace SimpleCodingQuestions
{
/// <summary>
/// Perform Binary Search given a pre-sorted list
/// of elements that implenent the IComparable interface
/// </summary>
/// <typeparam name="T">type of elements being searched</typeparam>
public class BinarySearch<T> where T: class, IComparable<T>
{
public static bool Search(T[] input, T target)
{
// null's cannot exist
if (target == null)
return false;
// define the search range
int low = 0;
int high = input.Length - 1;
// divide and conquer the list now
while (low <= high)
{
// find the mid point
int mid = (low + high)/2;
// compare the mid element with target
int compareResult = target.CompareTo(input[mid]);
if (compareResult < 0)
{
// discard right and recompare in left
high = mid - 1;
}
else if (compareResult > 0)
{
// value is more than mid
// discard left and recompare in right
low = mid + 1;
}
else
{
// we found our guy
return true;
}
}
// element not found
return false;
}
}
}
Binary search is good in cases where the collection is not modified often as that would require a re-sorting (or inserting in a sorted manner) each time a new element is inserted or deleted. In the next post, we will discuss another method of searching: Hash based search.
Hi There,
ReplyDelete10/10 !!! Thank you for making your blogs an embodiment of perfection and simplicity. You make everything so easy to follow.
This is my code. In the call to new B(), first the constructor for A is called and setI() is in there. Why it calls B.setI() while executing the constructor of A?
Java Code:
1
public class Test {
public static void main(String[] args) {
new A();
new B();
}
}
class A {
int i = 0;
public A() {
System.out.println("Constr A");
setI(5);
}
public void setI(int i) {
System.out.println("set in A");
this.i = 2 * i;
}
}
class B extends A {
public B() {
System.out.println("Constr B");
}
It was cool to see your article pop up in my google search for the process yesterday. Great Guide.
Keep up the
good work!
Thank you,
Great Article
ReplyDeleteIEEE Final Year Projects for CSE
IEEE Project Centers in Chennai
Hey what a brilliant post I have come across and believe me I have been searching out for this similar kind of post for past a week and hardly came across this. Thank you very much and will look for more postings from you. Binary options recovery
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteBinary Options Trading Strategy PDF does not guarantee winnings. However, it helps increase your chances of maximizing your potential profits.
ReplyDeleteAivivu - đại lý vé máy bay, tham khảo
ReplyDeletevé máy bay đi Mỹ hạng thương gia
mua vé máy bay về vn từ mỹ
giá vé máy bay đi Los Angeles
vé máy bay từ canada về việt nam bao nhiêu tiền
Big thanks to you for sharing such great information.
ReplyDeleteuser experience company