logo

Snefru: Learning Programming with C

  • Snefru: Learning Programming with C

Preface

  • What about programming?
  • Principles of using this textbook

Book Chapters

  • 1. Introduction to Programming Computers
    • 1.1. The Basic Structure of Computers
    • 1.2. Binary representation in memory
    • 1.3. Development Cycle
    • 1.4. Write Simple C Programs
  • 2. Data representation and operations
    • 2.1. Double data type for real numbers
    • 2.2. Data types and representation
    • 2.3. Operations
    • 2.4. Math library
    • 2.5. Random numbers
    • 2.6. Exercises
  • 3. Decision-Making Statements
    • 3.1. If-statements
    • 3.2. Multiple Conditions
    • 3.3. Nested-if statements
    • 3.4. Exercises
  • 4. Repetition
    • 4.1. While Loop
    • 4.2. Do-while loop
    • 4.3. For loops
    • 4.4. Nested loops
    • 4.5. Debugging for loops
    • 4.6. Exercises
  • 5. Functions
    • 5.1. Functions
    • 5.2. Communicate from a function
    • 5.3. Variable scope
    • 5.4. Pass more values to a function
    • 5.5. Exercises
  • 6. Pointers
    • 6.1. Why do we need pointers?
    • 6.2. What are pointers?
    • 6.3. How to use pointers to communicate more with functions?
    • 6.4. Rules defining scope of variables
    • 6.5. Goldbach conjecture
    • 6.6. Exercises
  • 7. Arrays
    • 7.1. Why and how to use arrays?
    • 7.2. What are arrays, and how are they stored?
    • 7.3. How do we pass an array to a function?
    • 7.4. Exercises
  • 8. Dynamic Memory Allocation
    • 8.1. What is dynamic memory allocation?
    • 8.2. Exercises
  • 9. Multi-dimensional Arrays
    • 9.1. Why and how to use 2D arrays?
    • 9.2. How do we pass a 2D array to a function?
    • 9.3. Dynamic Memory Allocation of 2D Arrays
    • 9.4. Exercises
  • 10. Strings
    • 10.1. What are strings?
    • 10.2. Input/Output Strings
    • 10.3. String Functions
    • 10.4. Array of Strings
    • 10.5. Exercises
  • 11. Recursion
    • 11.1. Recursive functions by definition
    • 11.2. Recursion in Patterns
    • 11.3. Recursion in arrays
    • 11.4. Exercises
  • 12. Data Structures
    • 12.1. What are data structures?
    • 12.2. Pointers to Data Structures
    • 12.3. Exercises
  • 13. Linked Lists
    • 13.1. Why linked lists?
    • 13.2. Form a linked list
    • 13.3. Insert nodes into a linked list
    • 13.4. Delete nodes in a linked list
    • 13.5. Exercises
  • 14. Sorting
    • 14.1. Insertion Sort
    • 14.2. Selection Sort
    • 14.3. Bubble sort
    • 14.4. Exercises
  • 15. Searching
    • 15.1. Linear/Sequential Search
    • 15.2. Binary Search
    • 15.3. Exercises

Appendix: Additional information

  • Appendix: Additional Resources
  • Set up Visual Studio Code
  • More Extensions in VS Code
  • Coding style
  • Debugging
  • Basic UNIX Commands
Powered by Jupyter Book
  • repository
  • open issue
  • .md
Contents
  • 15.2.1. Pseudocode
  • 15.2.2. Implementation
  • 15.2.3. Recursive Implementation

Binary Search

Contents

  • 15.2.1. Pseudocode
  • 15.2.2. Implementation
  • 15.2.3. Recursive Implementation

15.2. Binary Search#

Searching for an element in a sorted array is quick. Think of having a pile of booklets with names sorted in ascending order. Say you want to find the booklet with the name “Snefru”. You can start at the middle of the pile and check if the name is “Snefru”. If it is, you are done. If it is not, you can check if the name is before or after “Snefru”. If it is before, you can discard the second half of the pile. If it is after, you can discard the first half of the pile. You can repeat this process until you find the booklet with the name “Snefru”.

This method that we just discussed is called binary search. It is called binary search because it searches the list in a binary fashion, checking the middle element of the list and then discarding half of the list based on the result.

Given an array of seven elements named list as shown in the figure below, we want to look for item \(9\).

Binary Search Array

The algorithm for binary search is as follows:

  1. Define the limits of the array using variables low and high. We can do so by initially setting low = 0 and high = length of array - 1. Since we want to look at the middle element, we can hold its index in middle = (low + high)/2.

    Look in Middle
  2. Since the value at index middle is not equal to item, which is 9, we need to continue looking for item. We can check if list[middle] < item. If it is, we can discard the first half of the list. If it is not, we can discard the second half of the list. In our case, list[middle] is 7, which is less than item, which is 9. Therefore, we can discard the first half of the list. We can do this by setting low = middle + 1.

    Look in Right Subarray
  3. We can repeat step \(1\) and \(2\) but on the smaller right sub-array until we find item. In our case, low is 4 and high is 6. This makes middle = 5. Since list[middle] is 10, which is less than item, which is 9, next we can discard the second half of the sub-array (after middle).

    Look in Middle of Right Subarray
  4. We can discard the second half of the sub-array by setting high = middle - 1. After discarding the second half of the array, we have low = 4 and high = 4. This makes middle = 4.

    Look in Left Subarray
  5. Since list[middle] is 9, which is equal to item, we have found item in the array.

    Look in Middle of Left Subarray

When not found!

If item in our example was 8, we would NOT have found it at index 4. However, the algorithm will continue with setting high = middle - 1. This would make high = 3, and low remains 4. The algorithm should terminate when low > high. This means that the algorithm has searched the entire array and has not found item.

15.2.1. Pseudocode#

To highlight the main steps of binary search, we can write the algorithm in pseudocode as follows:

  1. Set low = 0 and high to the length of the array - 1.

  2. Look at the element at index middle = (low + high)/2.

  3. If the element at index middle is equal to item, return middle.

  4. If the element at index middle is less than item, the item could be in the right sub-array. Set low = middle + 1 to look at the right sub-array and go to step \(2\).

  5. Otherwise, set high = middle - 1 to look at the left sub array and go to step \(2\).

  6. If low > high, return -1 to indicate that item was not found.

15.2.2. Implementation#

To implement binary search, we need to write a function that takes in an array, size of the array and an item to search for. The function should return the index of the item if it is found in the array. If the item is not found, the function should return -1. Download the following code binary-search.c if you want to play with it.

Code


#include <stdio.h>

int binarySearch(int list[], int listLength, int item) { int low = 0; int high = listLength - 1; int middle;
while (low <= high) { middle = (low + high) / 2; if (item == list[middle]) return middle; else if (item < list[middle]) high = middle - 1; else low = middle + 1; } return -1; }
int main() { int list[] = {1, 3, 5, 7, 9, 10, 12}; printf("Found 9 at index %d\n", binarySearch(list, 7, 9)); return 0; }

In line \(17\), we have exited from the while loop. This means that we have searched the entire array and have not found item. Therefore, we return -1 to indicate that item was not found.

15.2.3. Recursive Implementation#

We can also implement binary search recursively.

Thinking recursively, as we discussed in Section 11.2.1, requires us to think about a smaller problem. In the case of binary search, we can think about the smaller problem of searching a smaller sub-array. This would be our recursive case. Our base/terminating case is when we have searched the entire array and have or have not found item.

How would we reduce the size of the array from one function call to the next recursive function call? We did a similar thing when we implemented isPalindrome function recursively inSection 11.3.2. The idea is to communicate with the next recursive function call the new limits of the array, i.e. the values of low and high.

Similarly, in our recursive binary search implementation below, we pass the values of low and high to the next recursive function call. We can do so by passing the values of low and high as arguments to the recursive function call.

Code

 1int binarySearchHelper(int list[], int low, int high, int item) {
 2  if (high < low)  // failure - item not in list
 3    return -1;
 4
 5  int middle = (low + high) / 2;
 6  if (item == list[middle])  // success
 7    return middle;
 8
 9  else if (item < list[middle])  // try bottom half
10    return binarySearchHelper(list, low, middle - 1, item);
11
12  else  // try top half
13    return binarySearchHelper(list, middle + 1, high, item);
14}

In line \(1\), we pass the array list, the values of low and high and the item to search for as arguments to the recursive function call. Initially, we can call the function to set low to 0 and high to the length of the array - 1.

Lines \(2\)–\(3\) handle the base case. If high is less than low, we have searched the entire array and have not found item. Therefore, we return -1 to indicate that item was not found.

Lines \(6\)–\(7\) handle another base case when we found item in the array. If item is equal to list[middle], we return middle to indicate that we have found item in the array.

Lines \(9\)–\(10\) handle the recursive case when item is less than list[middle]. In this case, we can discard the second half of the array by setting high = middle - 1 to the next recursive call. We can then call the recursive function to search the left sub-array by binarySearchHelper(list, low, middle - 1, item). The return before the recursive function call is important. This ensures that the value returned by the recursive function call is returned by the function. You can drop the return statement if it was a void function, but since it should return an int, we need to return the value returned by the recursive function call.

Lines \(12\)–\(13\) handle the recursive case when item is greater than list[middle]. In this case, we can discard the first half of the array by setting low = middle + 1 to the next recursive call. We can then call the recursive function to search the right sub-array by binarySearchHelper(list, middle + 1, high, item).

We can see that the values of low and high are updated in the recursive function call. This is how we reduce the size of the array from one function call to the next recursive function call.

Reduce number of arguments I would like to point out that functions with several arguments passed is not ideal, as someone may forget how to call the recursive function. We can improve this! We can implement a function that takes three arguments, an array, the size of the array and an item to search for. The function can then call the recursive function with the values of low and high set to 0 and the length of the array - 1, respectively. This is what we do in the following implementation. Download the following code binary-search-recursive.c if you want to play with it.

Code


#include <stdio.h>

int binarySearchHelper(int list[], int low, int high, int item); int binarySearchRecursive(int list[], int listLength, int item);
int main(){ int list[] = {1, 3, 5, 7, 9, 10, 12}; printf("Found 9 in index %d", binarySearchRecursive(list, 7, 9)); return 0; }
int binarySearchRecursive(int list[], int listLength, int item) { return binarySearchHelper(list, 0, listLength - 1, item); }
int binarySearchHelper(int list[], int low, int high, int item) { if (high < low) // failure - item not in list return -1;
int middle = (low + high) / 2; if (item == list[middle]) // success return middle; else if (item < list[middle]) // try bottom half return binarySearchHelper(list, low, middle - 1, item); else // try top half return binarySearchHelper(list, middle + 1, high, item); }

In lines \(12\)–\(14\), we call the recursive function binarySearchHelper with the values of low and high set to 0 and the length of the array - 1, respectively. As a developer, you can later just sell this function to your users, and they can call it with just three arguments, an array, size of the array and an item to search for. The function will then call the recursive function with the values of low and high set to 0 and the length of the array - 1, respectively.

Quiz

0 Questions

X

previous

15.1. Linear/Sequential Search

next

15.3. Exercises

By Salma Emara et al.
© Copyright 2022–2025.