Binary Search Algorithm

martin_ndegwa — Sun, 18 Jun 2023 05:16:54 +0000

What is binary search algorithm?
Well, it's an algorithm :)
An algorithm is a set of finite instructions or rules used to solve a particular problem. A binary search algorithm takes a sorted input of a list of elements, such as numbers. When the element you are searching for is in the list, the algorithm returns where it is located.

Why use Binary Search?
Binary search is well suited for a large input of elements.It is more efficient than a linear search where a case of say 1024 elements would take 1023 steps (worst case) or so to get an element near the 1024 mark. A binary search would take log n time to get an element from the same(worst case). log 1024 = 10 this means it would take 10 steps since 2 to the power of 10 is 1024. Simply log n here means logarithmic time and it's computed as log n to the base of 2 in layman's terms think of it as "How many 2s do we multiply together to get 1024?"
The time is shortened quite impressively right?

Now let's see how it works
The code here is in Python, but the logic is the same for other programming languages. Okay, so binary search works only with a sorted list and you'll keep track of the part of the list to search through, at first it's the entire array:

low = 0
high = len(list) - 1

Each time you check the middle element;

mid = (low + high) / 2
guess = list[mid]

Here your guess is that just maybe the element you are searching for is in the middle of your list, if the guess is too low, you'll adjust low accordingly:

low = mid + 1

And if the guess is to high, you update high; Here is the full python code

"""binary search"""
def binary_search(list: [int], num: int) -> int:
    """num is the searched number in the list"""
    low = 0
    high = len(list) - 1
    list.sort() # sort the list


    while(low <= high):
        # get the middle element
        mid = (low + high) // 2
        guess = list[mid]

        if guess == num:
            return mid
        if guess > num:
            high = mid - 1
        else:
            low = mid + 1
    return 0

if __name__ == '__main__':
    number_to_search = 5
    list = [1,8,9,3,4,6,5,10,7]
    print(binary_search(list, number_to_search))

The code returns 3 which is the position of 5 in the 0-based index of the sorted list.
You can try out the code with larger inputs and see the beauty of it. Alright that's it, Happy Coding!

What happens when you type www.google.com and hit enter on your keyboard?

martin_ndegwa — Fri, 12 May 2023 09:03:44 +0000

Introduction.

The Uniform Resource Locator(URL), which is a reference to that web resource, identifies the place on a computer network where a web resource is located and how it can be retrieved. Let's look at what happens when you type in a URL, like https://ww.google.com, in your browser and press Enter.

A URL

When we look at the (URL), the first word stands for Hypertext Transfer Protocol Secure "HTTPS." It is an internet protocol that communicates with the server to handle the browser's request. The domain google.com
includes the "www" subdomain. The URL is first sent to a Domain Name Server (DNS), a computer with a database of public IP addresses and the hostnames that correspond to them. The initial action that takes place when you search for any URL in the browser is referred to as a DNS query. The reason is that, unlike IP addresses, hostnames are strings with a domain name suffix that the servers cannot understand.

TCP/IP connection

Now that we have the corresponding IP address to our domain name, the next process is a TCP three-way handshake between both the browser (client) and server: synchronize (a.k.a. SYN), and acknowledge (a.k.a. ACK). The client here sets an initial SYN sequence number; the server also has its own sequence number, which increments the client’s SYN. The server then sends back a (SYN/ACK) packet to the client and awaits the client's ACK by incrementing its SYN.

HTTPS/SSL

Once the TCP/IP connection has been established, the browser proceeds to communicate with the server using a secure protocol (HTTPS). This protocol defines different types of requests (e.g., GET, POST, and PUT), which are secured by a security protocol called Secure Sockets Layer that encrypts and decrypts the data from the client to the server infrastructure at the load balancer.

Load Balancer

The load balancer distributes website user requests across a number of servers when there is a high volume of requests in order to avoid a single point of failure (SPOF) or downtime.

The Firewall, also known as the Great Wall

The firewall analyzes incoming traffic using pre-established rules and filters traffic from untrusted or shady sources to prevent attacks from hackers who can intercept user traffic. Users are permitted to connect to a web server that will be assigned by the load balancer if their requests are not malicious or suspicious.

Web Server and Application Server

Now let’s do a recap. First, we started by doing a DNS query, which helps get an IP address associated with the domain name of our website. The IP address is sent back to our browser client, which sends the IP address to the server, where a TCP/IP connection is established. When this is done, the browser can now communicate with the server through the HTTPS protocol. The encryption and decryption of data between the server and the client are done through a standard security protocol called Secure Sockets Layer (SSL). The load balancer can then serve the web server with users’ requests if the firewall allows the incoming traffic.
Let’s define a web server. A web server is a software and hardware system that only handles HTTP and HTTPS requests and serves static content like simple HTML pages, plain text files, and images.
The application server, on the other hand, runs behind a web server and in front of a database management system (DBMS). Its main purpose is to generate dynamic content support for an application’s development and delivery, thus providing the business logic behind the application.

Data Management

Database Management System (DBMS), A program that allows the interaction with a database (an organized collection of structured information or data stored in a computer system) to define, manipulate, retrieve, and manage the data according to the request

Conclusion

This is the entire process when you type https://google.com and hit enter. It might look like a lot, but this happens within a few seconds, and you get dynamic content served to your browser through a secured HTTPS connection. I hope the explanation is easy to understand.

DEV Community: martin_ndegwa