Binary search for strings python

Question

I'm relatively new to python(3.3) and I'm just trying to do a binary search through a list of words, and cant figure out how to fix my operand types when it comes down to looping through the indices... I continue to get the TypeError. Cant figure out any way around it

Nội dung chính Show

Can I use binary search on strings?
How do you write a binary search in Python?
Is there binary search in Python?
What is binary search in Python with example?

def find(L, target):
    start = 0
    end = len(L) - 1

    while start <= end: 
        middle = (start + end)// 2 
        midpoint = L[middle]
        if midpoint > target:
            end = midpoint - 1
        elif midpoint < target:
            start = midpoint + 1
        else:
            return midpoint

I'm calling the function as so:

L = ["Brian", "Meg", "Peter", "Joe", "Stewie", "Lois"]

find(L, "Joe")

tdelaney

66.1k5 gold badges74 silver badges106 bronze badges

asked Dec 17, 2015 at 5:28

7

Your logic seems fine, except for the input and the bug with incrementing and decrementing midpoint instead of middle.

def find(L, target):
    start = 0
    end = len(L) - 1

    while start <= end:
        middle = (start + end)/ 2
        midpoint = L[middle]
        if midpoint > target:
            end = middle - 1
        elif midpoint < target:
            start = middle + 1
        else:
            return midpoint

L = ["Brian", "Joe", "Lois", "Meg", "Peter", "Stewie"] # Needs to be sorted.

print find(L, "Peter")

Bhargav Rao

47.3k27 gold badges121 silver badges137 bronze badges

answered Dec 17, 2015 at 5:40

jianweichuahjianweichuah

1,3971 gold badge8 silver badges22 bronze badges

2

def find(L, target):
    start = 0
    end = len(L) - 1
    while start <= end:
        middle = (start + end)// 2
        midpoint = L[middle]
        if midpoint > target:
            end = middle - 1
        elif midpoint < target:
            start = middle + 1
        else:
            return midpoint

    L = ["Brian", "Joe", "Lois", "Meg", "Peter", "Stewie"]
    L = sorted(L)
    print(find(L, "Lois"))

As pointed out by others, use middle instead of midpoint

And to optimally use binary search, sort the list first

Vivek Sable

9,5063 gold badges36 silver badges51 bronze badges

answered Dec 17, 2015 at 5:44

Prashant YadavPrashant Yadav

5011 gold badge10 silver badges25 bronze badges

1

def binarySearchOnString(arr, x):
        l = 0
        r = len(arr) - 1
        while (l <= r): 
            m = (l + r) // 2 
            if (arr[m] == x): 
                return m
            elif (arr[m] < x): 
                l = m + 1
            else: 
                r = m - 1
        return -1  #   If element is not found  then it will return -1

answered Oct 8, 2020 at 5:50

SunnySunny

1,04711 silver badges14 bronze badges

View Discussion

Improve Article

Save Article

Read

Discuss

View Discussion

Improve Article

Save Article

Given a sorted array of Strings and a String x, find an index of x if it is present in the array.

Examples:

Input :  arr[] = {"contribute", "geeks", "ide", "practice"}, x = "ide"
Output :  2
The String x is present at index 2.

Input :  arr[] = {"contribute", "geeks", "ide", "practice"}, x = "zz"
Output :  -1
The String "zz" is not present.

Prerequisites: Binary Search, String Comparison in Java
The idea is to compare x with the middle string in the given array. If it matches, then returns mid, else if it is smaller than mid, then search in the left half, else search in the right half.

Implementation:

C++

#include

using namespace std;

int binarySearch(string arr[], string x,int n)

{

int l = 0 ;

int r = n - 1;

while (l <= r)

{

int m = l + (r - l) / 2;

int res = -1000;

if (x == (arr[m]))

res = 0;

if (res == 0)

return m;

if (x > (arr[m]))

l = m + 1;

else

r = m - 1;

}

return -1;

}

int main()

{

string arr[] = { "contribute", "geeks", "ide", "practice"};

string x = "ide";

int n = 4;

int result = binarySearch(arr, x,n);

if (result == -1)

cout << ("Element not present");

else

cout << ("Element found at index ") << result;

}

Java

class GFG {

static int binarySearch(String[] arr, String x)

{

int l = 0, r = arr.length - 1;

while (l <= r) {

int m = l + (r - l) / 2;

int res = x.compareTo(arr[m]);

if (res == 0)

return m;

if (res > 0)

l = m + 1;

else

r = m - 1;

}

return -1;

}

public static void main(String []args)

{

String[] arr = { "contribute", "geeks", "ide", "practice"};

String x = "ide";

int result = binarySearch(arr, x);

if (result == -1)

System.out.println("Element not present");

else

System.out.println("Element found at "

+ "index " + result);

}

Python3

def binarySearch(arr, x):

l = 0

r = len(arr)

while (l <= r):

m = l + ((r - l) // 2)

res = (x == arr[m])

if (res == 0):

return m - 1

if (res > 0):

l = m + 1

else:

r = m - 1

return -1

if __name__ == "__main__":

arr = ["contribute", "geeks",

"ide", "practice"];

x = "ide"

result = binarySearch(arr, x)

if (result == -1):

print("Element not present")

else:

print("Element found at index" ,

result)

C#

using System;

class GFG {

static int binarySearch(String[] arr, String x)

{

int l = 0, r = arr.Length - 1;

while (l <= r) {

int m = l + (r - l) / 2;

int res = x.CompareTo(arr[m]);

if (res == 0)

return m;

if (res > 0)

l = m + 1;

else

r = m - 1;

}

return -1;

}

public static void Main(String []args)

{

String[] arr = { "contribute", "geeks", "ide", "practice"};

String x = "ide";

int result = binarySearch(arr, x);

if (result == -1)

Console.WriteLine("Element not present");

else

Console.WriteLine("Element found at "

+ "index " + result);

}

PHP

function binarySearch($arr, $x)

{

$l = 0;

$r = count($arr);

while ($l <= $r)

{

$m = $l + (int)(($r - $l) / 2);

$res = strcmp($x, $arr[$m]);

if ($res == 0)

return $m - 1;

if ($res > 0)

$l = $m + 1;

else

$r = $m - 1;

}

return -1;

}

$arr = array("contribute", "geeks",

"ide", "practice");

$x = "ide";

$result = binarySearch($arr, $x);

if ($result == -1)

print("Element not present");

else

print("Element found at index " .

$result);

?>


Javascript
Output
Element found at index 2

 
Can I use binary search on strings?
Binary search is searching technique that works by finding the middle of the array for finding the element. For array of strings also the binary search algorithm will remain the same. But the comparisons that are made will be based on string comparison.
How do you write a binary search in Python?
Implement a Binary Search in Python.
 # Iterative Binary Search Function method Python Implementation..
 # It returns index of n in given list1 if present,.
 # else returns -1..
 def binary_search(list1, n):.
 low = 0..
 high = len(list1) - 1..
 mid = 0..
 while low <= high:.
 
Is there binary search in Python?
A Python binary search is an algorithm that finds the position of an element in an ordered array. Binary searches repeatedly divide a list into two halves. Then, a search compares if a value is higher or lower than the middle value in the list.
What is binary search in Python with example?
Binary search is a searching algorithm which is used to search an element from a sorted array. It cannot be used to search from an unsorted array. Binary search is an efficient algorithm and is better than linear search in terms of time complexity. The time complexity of linear search is O(n).

programming python Python binary search Binary search Python Binary search alphabet Binary search C++

Binary search for strings python

C++

Java

Python3

C#

PHP

Javascript

Can I use binary search on strings?

How do you write a binary search in Python?

Is there binary search in Python?

What is binary search in Python with example?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội