Binary Search

Introduction​

Binary search is a searching algorithm, used to search for an element in an array. It follows a unique approach which reduces the time complexity as compared to linear search. However, to use binary search, the array must be sorted.

Video Explanation​

Watch

Binary Search Visualization​

Implementation​

Let us see how to implement binary search in Java:

        //let element to be found=target
		int low=0;
		int high=n-1; //where n is the length of the sorted array
        int mid; //represents the mid index of the array

        int flag=0; //element not yet found 

		while(low<=high) {

			mid=(low + high)/2;
			if(arr[mid]==target) {
				flag=1; //element found
				System.out.println("Target found!");
				break;
			}
			else if(arr[mid]<target) {
                // which means target is to the right of mid element
				low=mid+1;
			}
			else {
                //target is to the left of mid element
				high=mid-1;
			}
			
		}

		if(flag==0) {
			System.out.println("Target not found!");
		}

Implementation​

Let us see how to implement binary search in javascript:

function binarySearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;
    let flag = false; // element not yet found

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);

        if (arr[mid] === target) {
            flag = true; // element found
            console.log("Target found!");
            break;
        } else if (arr[mid] < target) {
            // target is to the right of mid element
            low = mid + 1;
        } else {
            // target is to the left of mid element
            high = mid - 1;
        }
    }

    if (!flag) {
        console.log("Target not found!");
    }
}

// Example usage
let arr = [1, 3, 5, 7, 9, 11];
let target = 7;
binarySearch(arr, target);

In this algorithm, the searching interval of the array is divided into half at every iteration until the target is found. This results in lesser comparisions and decreases the time required.

Dry Run Examples​

We will walk through two detailed dry run examples using the following sample sorted array:

Indices:   0   1   2   3   4   5   6   7   8   9
Array:   [ 2,  5,  8, 12, 16, 23, 38, 56, 72, 91 ]

Example 1: Target Element Exists (Target = 23)​

We search for the target value 23 in the array.

Step-by-Step Execution​

Iteration 1​

• Search Space: Index 0 to 9 (entire array).
• Pointers: low = 0, high = 9
• Midpoint Calculation: $\text{mid} = \text{low} + \frac{\text{high} - \text{low}}{2} = 0 + \frac{9 - 0}{2} = 4$
• Middle Element: arr[mid] = arr[4] = 16
• Visual Representation:

  Indices:    0   1   2   3  [4]   5   6   7   8   9
  Array:    [ 2,  5,  8, 12,  16, 23, 38, 56, 72, 91 ]
              ^                ^                   ^
             low              mid                 high
  

• Comparison & Decision:
  • arr[mid] ($16$) is less than target ($23$).
  • Since the array is sorted, the target must reside in the right half of the current search space.
  • We discard the left half by updating: low = mid + 1 = 5.

Iteration 2​

• Search Space: Index 5 to 9.
• Pointers: low = 5, high = 9
• Midpoint Calculation: $\text{mid} = 5 + \frac{9 - 5}{2} = 7$
• Middle Element: arr[mid] = arr[7] = 56
• Visual Representation:

  Indices:    0   1   2   3   4   5   6  [7]   8   9
  Array:    [ -   -   -   -   -  23, 38,  56, 72, 91 ]
                                 ^       ^       ^
                                low     mid     high
  

• Comparison & Decision:
  • arr[mid] ($56$) is greater than target ($23$).
  • The target must reside in the left half of the remaining search space.
  • We discard the right half by updating: high = mid - 1 = 6.

Iteration 3​

• Search Space: Index 5 to 6.
• Pointers: low = 5, high = 6
• Midpoint Calculation: $\text{mid} = 5 + \frac{6 - 5}{2} = 5$
• Middle Element: arr[mid] = arr[5] = 23
• Visual Representation:

  Indices:    0   1   2   3   4  [5]   6   7   8   9
  Array:    [ -   -   -   -   -  23, 38,  -   -   -  ]
                                 ^   ^
                             low,mid high
  

• Comparison & Decision:
  • arr[mid] ($23$) is equal to target ($23$).
  • Target is found! We return index 5.

Summary of Execution (Success Case)​

Example 2: Target Element Does Not Exist (Target = 10)​

We search for the target value 10 in the same array.

Step-by-Step Execution​

Iteration 1​

• Pointers: low = 0, high = 9
• Midpoint: mid = 4, arr[mid] = 16
• Visual:

  Indices:    0   1   2   3  [4]   5   6   7   8   9
  Array:    [ 2,  5,  8, 12,  16, 23, 38, 56, 72, 91 ]
              ^                ^                   ^
             low              mid                 high
  

• Comparison: 16 > 10. Target is smaller, so search left half: high = mid - 1 = 3.

Iteration 2​

• Pointers: low = 0, high = 3
• Midpoint: mid = 0 + (3 - 0) / 2 = 1, arr[mid] = arr[1] = 5
• Visual:

  Indices:    0  [1]   2   3   4   5   6   7   8   9
  Array:    [ 2,  5,  8, 12,  -   -   -   -   -   -  ]
              ^    ^       ^
             low  mid     high
  

• Comparison: 5 < 10. Target is larger, so search right half: low = mid + 1 = 2.

Iteration 3​

• Pointers: low = 2, high = 3
• Midpoint: mid = 2 + (3 - 2) / 2 = 2, arr[mid] = arr[2] = 8
• Visual:

  Indices:    0   1  [2]   3   4   5   6   7   8   9
  Array:    [ -   -   8, 12,  -   -   -   -   -   -  ]
                      ^    ^
                  low,mid high
  

• Comparison: 8 < 10. Target is larger, so search right half: low = mid + 1 = 3.

Iteration 4​

• Pointers: low = 3, high = 3
• Midpoint: mid = 3, arr[mid] = arr[3] = 12
• Visual:

  Indices:    0   1   2  [3]   4   5   6   7   8   9
  Array:    [ -   -   -  12,  -   -   -   -   -   -  ]
                          ^
                     low,mid,high
  

• Comparison: 12 > 10. Target is smaller, so search left half: high = mid - 1 = 2.

Termination​

• State: low = 3, high = 2.
• Since low > high, the search space has collapsed completely, meaning the target element 10 is not present in the array.

Summary of Execution (Failure Case)​

Why Binary Search is Efficient​

Binary Search reduces the search space by half in every iteration, making it much faster than Linear Search for large sorted arrays.

• Time Complexity: $O(log n)$
• Space Complexity: $O(1)$

Advantages of Binary Search​

• Binary Search is much faster than Linear Search for large datasets.
• It reduces the search space by half in every step.
• Efficient for searching in sorted arrays.
• Widely used in competitive programming and real-world applications.

Real-World Applications​

• Searching contacts in a phonebook
• Searching words in a dictionary
• Database indexing
• Finding elements in large sorted datasets
• Used in many search-based applications

Time complexity:​

Linear/Sequential search: $O(n)$
Binary search : $O(log n)$

Points to Remember:​

• Binary search requires a sorted array.
• Works for 1 dimensional arrays.
• Faster and more efficient than sequential search.
• Uses the divide and conquer approach.
• Best if arrays are too long (large datasets).

Algorithm Tip​

Binary Search provides very fast searching but requires the array to be sorted first.

When to Use This Algorithm​

Use Binary Search when:

• The data is already sorted
• Fast searching is required
• Repeated searches are performed

Common Mistakes​

• Using Binary Search on unsorted arrays
• Forgetting to update left and right pointers correctly
• Incorrect midpoint calculation causing infinite loops

Practice Problems​