Binary Search Sorted Array

Objective

To implement a program to search an element in a list using binary search technique.

 

Theory

Binary search is a widely used algorithm for efficiently finding a specific value in a sorted collection of elements. It is an example of a divide and conquer strategy and is often more efficient than linear search, especially for large data. The algorithm functions by iteratively halving the segment of the list where the item might be located, progressively narrowing down the potential positions until only one remains. 

Algorithm

binary_search(arr, target): 

  1. Set low to 0 and high to the length of the array minus 1. 
  2. While low is less than or equal to high: 
    1.  Set mid to the floor of (low + high) / 2. 
    2. If the element at index mid is equal to the target, return mid (element found). 
    3. If the element at index mid is less than the target, update low to mid + 1 (search in the right half). 
    4. If the element at index mid is greater than the target, update high to mid - 1 (search in the left half). 
  3. If low is greater than high, the target is not present in the array. Return -1 (element not found). 

Pseudo Code

binarySearch(arr, x, low, high) 
    if low > high 
        return False  
    else 
        mid = (low + high) / 2  
        if x == arr[mid] 
            return mid 
        else if x > arr[mid]                 // x is on the right side 
            return binarySearch(arr, x, mid + 1, high) 
        else                                            // x is on the left side 
            return binarySearch(arr, x, low, mid - 1) 

In above pseudo code, the binary_search() function takes the input list 'arr', the indices of the lower and upper bounds of the search interval, and the target element 'x'. The function first checks if the search interval is not empty, i.e., if the 'high' index is greater than the 'low' index. If the search interval is not empty, the function calculates the middle index of the search interval using integer division. If the middle element is equal to the target element 'x', the function returns the index of the middle element. If the middle element is greater than the target element 'x', the function calls itself recursively with the lower half of the search interval, i.e., the 'low' index and 'mid-1'. If the middle element is smaller than the target element 'x', the function calls itself recursively with the upper half of the search interval, i.e., the 'mid+1' and 'high' index. The recursion continues until the target element is found, or the search interval is empty. 

 

Learning Outcomes 

By learning the Divide and Conquer algorithm to find the maximum value of an array, you can achieve several learning outcomes, including:

  • Understanding of the binary search algorithm: The program implements the binary search algorithm, which is an efficient way of searching for an element in a sorted array. Studying this program will help the learner understand the basic workings of the algorithm, its time complexity, and how it compares to other search algorithms.
  • Familiarity with recursion: The binary_search() function in the program uses recursion to implement the binary search algorithm. By studying this program, the learner will gain a better understanding of how recursion works and how it can be used to solve problems.
  • Ability to implement binary search algorithm in code: The program provides a practical example of how to implement the binary search algorithm in code using recursion. The learner will be able to apply this knowledge to implement the algorithm in their own programs and solve search problems efficiently.
  • Understanding the importance of sorting in search algorithms: The program assumes that the input array is sorted. Studying this program will help the learner understand the importance of sorting in search algorithms and how it affects the time complexity of the algorithm.
  • Debugging skills: The program provides an opportunity for the learner to practice their debugging skills. By studying the code and identifying any errors or bugs, the learner will develop their ability to read and understand code and troubleshoot issues in their own programs.