**Objective :** Write an algorithm to find an element in an sorted array

**Input:** A sorted array, arrA[] and an key

**Output :** Return true if element is found, else false.

**Approach:** The idea is to compare the middle element of array with the key, if key equal to the middle element , that’s it you have find your element, return true. If key is greater than the middle element, chuck out the first half of the array, you wont find your key in the first half and do the recursive search on the right half of the array and vice versa.

If(mid_element==key) return true; else if (mid>key) do recursive search on the right half of the array. else do recursive search on the left half of the array.

**Time Complexity: O(logN) **–since we are eliminating half of the array with every comparison.

**Complete Code:**

public class BinarySearch { | |

private int [] arrA; | |

private int number; | |

public BinarySearch(int [] arrA){ | |

this.arrA = arrA; | |

} | |

public Boolean Search(int low,int high, int number){ | |

if(low>high){ | |

return false; | |

} | |

int mid = low + ((high – low) / 2); | |

if(arrA[mid]==number)return true; | |

else if (arrA[mid]>number) return Search(low,mid–1,number); | |

else return Search(mid+1,high,number); | |

} | |

public static void main(String args[]){ | |

int [] a = {2,5,8,10,14,44,77,78,99}; | |

int number = 99; | |

BinarySearch b = new BinarySearch(a); | |

System.out.println("The "+ number + " present in array a ??? :" + b.Search(0, a.length–1, number)); | |

number = 76; | |

System.out.println("The "+ number + " present in array a ??? :" + b.Search(0, a.length–1, number)); | |

} | |

} |

Output:

The 99 present in array a ??? :true The 76 present in array a ??? :false

if (mid>key)

do recursive search on the left half of the array.

else

do recursive search on the right half of the array.

// Generic way to binary search any object types

public int binarySearch(Object[] a, Object key) {

// if(Objects.isNull(a) || Objects.isNull(key)) throw new IllegalArgumentException(“Invalid arguments”);

int low = 0;

int high = a.length-1;

int mid ;

while (low >> 1;

Comparable midVal = (Comparable) a[mid];

int cmp = midVal.compareTo(key);

if(cmp 0) {

high = mid-1;

}

else {

return mid;

}

}

return – (low+1);

}