In the world of computer science there are so many concepts and search is the one of the most important things. For example we have telephone directory without any index and suppose we need to find someone phone number, now can you imagine how difficult it would be? If it will not arrange in some logical way. Suppose we have some collection of data and we want to find something.
In computer language, there is so many searching algorithms like Linear, Binary etc.
Today we will discuss Binary Search.
Binary search works on sorted data collection. Suppose we have a collection of student’s name and we want to search that one particular student studies in that college or not. So first we have a need to get all students name in order. After that only we can use Binary Search Algorithm.
Binary Search Algorithm is very effective with Linear Search.
In Binary search, we divide the sorted list of data into two parts and then check whether the target value falls in the first half or second half. If target value falls in the second half then again we divide second half into two part and again check whether the target value falls in the first half or second half. This process will continue until we can divide the sorted list into two part.
Below is the code in Java, where we are storing the data into int array in increasing order and after that search some value by binarySearch function.
Binary Search Java example:-
public class MyBinarySearch
{
public static void main(String[] args)
{
int valueStore = 12;
int target = 104;
int[] arrayList = new int[valueStore];
for (int i = 0; i < valueStore ; i++)
arrayList[i] = i + 100;
System.out.print("List of Array is ");
for(Integer i : arrayList)
System.out.print(i + ", ");
System.out.println();
System.out.println("Position of Target value "+ target + " is " + binarySearch(arrayList, target));
}
private static int binarySearch(int[] arrayList, int target)
{
int start = 0;
int end = arrayList.length - 1;
while(start <= end)
{// Line 1
int middle = (start + end)/2 ;// Line 2
if (target < arrayList[middle])
{// Line 3
end = middle - 1;// Line 4
} else if ( target > arrayList[middle])
{// Line 5
start = middle + 1;// Line 6
} else
{// Line 7
return middle;// Line 8
}
}
return -1;// Line 9
}
}
Explanation of binarySearch java function:-
First store the start and last index of array,
And while loop will execute until we traveled full array, or we get location of the target value
Now we get middle point of array.
Now target (104) is checking that it is less than middle value (105), yes it is fall, now it will set new end point as middle -1 (4) and middle point set index 2.
Now target (104) is checking that it is less than middle value (102), no it does not fall, so it will check that target is greater than middle value 102, yes it fall, so it will set new start point as middle + 1 (3) and middle point set as index 3.
Now target (104) is checking that it is less than middle value (103), no it does not fall, so it will check that target is greater than middle value 103, yes it fall, so it will set new start point as middle + 1 (4) and middle point set as index 4.
So now start point, middle point, and end point all three set a 4. I.e. while loop will terminate with Location of the target is at index 4.
