Day26.1 - Searching in java: Binary search

Binary Search:

Definition:

Binary search oru efficient algorithm,ithu sorted array la oru element ah thedura method.Divide and conquer approach use pannum athu search range ah rendu panga pirichu (half ah divide pannitu) check pannum.

Time Complexity:

Best case:

O(1) — target middle la irundha first check la kandupidichurum

Worst and Average case:

O(log n) — because every time, search space ah half pannitu pogum. Adhan logarithmic time complexity.

Condition:

Array must be sorted — Binary search unsorted arrays la work agadhu!So,ascending or descending order la irukkanum data.

Simple Definition:

Middle element ah check panni,target smaller ah irundha left side la pogum,target bigger ah irundha right side la pogum ippadi half half ah split pannitu search pannum.

Example Program:

package javaprogram;

public class Binarysearch {
public static void main(String[] args) 
{

// TODO Auto-generated method stub

int[]arr={10,15,20,25,30,35,40,45}; 
         //0 ,1 ,2 ,3 ,4 ,5 ,6 ,7

int key=40;
int min_index=0;
int max_index=arr.length-1;
while(min_index<=max_index)
{
int mid_index=(min_index+max_index)/2;  //3
if(arr[mid_index]==key)
{
System.out.println("key is presented in "+ mid_index);
break;
}
else if (key>arr[mid_index]) //3
{
min_index = mid_index+1;   //3+1=4
//System.out.println("key is presented in "+min_index);
}
else if(key>arr[mid_index]) 
{
min_index = mid_index -1;
System.out.println("key is presented in "+min_index);
}
}
}
}