<p><span style="color: #008000;"><strong>Binary search</strong></span> works on sorted arrays. Binary search begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less than the middle element, the search continues in the lower half of the array. If the target value is greater than the middle element, the search continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration.</p>
<h4><strong><span style="color: #000080;">Algorithm:</span></strong></h4>
<ul>
<li><strong><span style="color: #0000ff;">step 1 :</span></strong> Compare x(item To Search) with the middle element.</li>
<li><span style="color: #0000ff;"><strong>step 2 : </strong></span> If x matches with middle element, return the mid index.</li>
<li><span style="color: #0000ff;"><strong>step 3 :</strong></span> Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.</li>
<li><strong><span style="color: #0000ff;">step 4 :</span></strong> Else (x is smaller) recur for the left half.</li>
</ul>
<h4><strong><span style="color: #000080;">Iterative implementation of Binary Search</span></strong></h4>
<pre style="padding-left: 30px;"><strong><code>public class Search {

<span style="color: #0000ff;">//return index of item if it is present in arr[]</span>
<span style="color: #0000ff;">//else return -1</span>
public int binarySearch(int arr[], int u,int l, int item) 
 {
 while (l <;= u) 
 { 
 int mid = (l + u) / 2;
<span style="color: #0000ff;"> //check if item is present at middle</span>
 if (arr[mid] == item) 
 return mid; 
<span style="color: #0000ff;"> //if item is smaller ignore right half</span>
 else if (arr[mid] >; item)
 u = mid - 1;
 else
<span style="color: #0000ff;"> //if item is greater ignore left half
</span> l = mid + 1;
 }
<span style="color: #0000ff;"> //return -1 if element is not found
</span> return (-1);
 }

public static void main(String[] strr) 
{
<span style="color: #0000ff;">//l for lower </span>
<span style="color: #0000ff;">//u for upper </span>
int u, l, itemToSearch;
int arr[] = {1, 2, 10, 13, 17, 29, 33, 42, 49, 98, 100};
u = arr.length - 1;
l = 0;
itemToSearch = 10;
int index = new Search().binarySearch(arr,u,l,itemToSearch);
if (index==-1)
System.out.println("item not exist");
else
System.out.println("Item"+" " +itemToSearch+" " + "found at index :" + index + " and " +"position :" + (index+1));
}
} </code></strong></pre>
<h4><span style="color: #000080;"><strong>Output:</strong></span></h4>
<p><strong><span style="color: #0000ff;">Item 10 is found at index :2 and position :3</span></strong></p>
<!-- WP QUADS Content Ad Plugin v. 2.0.98.1 -->
<div class="quads-location quads-ad2" id="quads-ad2" style="float:none;margin:0px;">

</div>

<h4><strong><span style="color: #000080;"> Recursive implementation of Binary Search</span></strong></h4>
<pre style="padding-left: 30px;"><strong><code>public class Search {
 
public int binarySearch(int arr[], int l,int u, int item) 
 { 
 if (u>;=l)
 { 
 int mid = l + (u - l)/2; 
 if (arr[mid] == item){ 
 return mid; 
 } 
 if (arr[mid] >; item){ 
<span style="color: #0000ff;"> //search in left subarray</span>
 return binarySearch(arr, l, mid-1, item); 
 }
 else{ 
<span style="color: #0000ff;"> //search in right subarray</span> 
 return binarySearch(arr, mid+1, u, item);
 } 
 } 
 return -1; 
 }
 
public static void main(String args[]){ 
<span style="color: #0000ff;">//l for lower </span>
<span style="color: #0000ff;">//u for upper </span>
int u, l, itemToSearch;
int arr[] = {1, 2, 10, 13, 17, 29, 33, 42, 49, 98, 100};
u = arr.length - 1;
l = 0;
itemToSearch = 10;
int index = new Search().binarySearch(arr, l, u, itemToSearch); 
if (index==-1)
System.out.println("item not exist");
else
System.out.println("Item"+" " +itemToSearch+" " + "found at index :" + index + " and " +"position :" + (index+1));
}
}</code></strong></pre>
<p> ;</p>
<h4><span style="color: #000080;"><strong>Output:</strong></span></h4>
<p><strong><span style="color: #0000ff;">Item 10 is found at index :2 and position :3</span></strong></p>
<h4><span style="color: #000080;"><strong>Time complexity</strong></span></h4>
<p>As we dispose off one part of the search case during every step of binary search, and perform the search operation on the other half, this results in a worst case time complexity of O(Log n) ,where n is the no of elements in the array.